Cod sursa(job #2889818)

Utilizator bem.andreiIceman bem.andrei Data 13 aprilie 2022 13:05:41
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("laser.in");
ofstream w("laser.out");
const long double eps = 1e-8;
const long double pi = (long double) 2 * acos((long double) 0);
int n, p[1013], m;
bitset<1013> a[1013];
pair<long double, long double> A[1013];
vector<long double> ans, v, bisect;
long double unghi(int x, int y)
{
    long double angle = atan2(y,x) * 180 / pi;
    if (angle < 0)
    {
        angle += 360;
    }
    return angle;
}

bool contain(long double x, long double y, long double z)
{
    if(y-x > 180)
    {
        return (z<x || z>y);
    }
    return (x<z && z<y);
}
int main()
{
    r>>n;
    for(int i=1; i<=n; i++)
    {
        int x1, y1, x2, y2;
        r>>x1>>y1>>x2>>y2;
        long double u1 = unghi(x1, y1), u2 = unghi(x2, y2);
        if(u1 > u2)
        {
            swap(u1, u2);
        }
        A[i] = {u1, u2};
        v.push_back(u1);
        v.push_back(u2);
    }
    sort(v.begin(), v.end());
    m = v.size();
    for(int i=0; i<m-1; i++)
    {
        bisect.push_back( (v[i]+v[i+1])/2 );
    }
    bisect.push_back( ( v[0]+360 + v[m-1] )/2 );
    if(bisect.back() > 360)
    {
        bisect.back() -= 360;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            a[i][j] = contain(A[i].first, A[i].second, bisect[j-1]);
        }
        int xr;
        r>>xr;
        a[i][m+1] = xr;
    }
    for(int i=1; i<=n; i++)
    {
        int j;
        for( j=1; j<=m; j++)
        {
            if(a[i][j])
            {
                break;
            }
        }
        if(j==m+2)
        {
            continue;
        }
        p[i] = j;
        for(int j=1; j<=n; j++)
        {
            if(i!=j && a[j][p[i]])
            {
                a[j] ^= a[i];
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(p[i]!=0 && a[i][m+1]!=0)
        {
            ans.push_back(bisect[p[i]-1]);
        }
    }
    w<<(int)ans.size()<<"\n";
    for(auto it : ans)
    {
        w<<fixed<<setprecision(10)<<it<<"\n";
    }
    return 0;
}