Cod sursa(job #2721101)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 11 martie 2021 16:08:47
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
const ld eps = 1e-8;
const ld PI = (ld) 2 * acos((ld) 0);

int X1, Y1, X2, Y2, i, n, j, p[1234], xr, m;
bitset<1234> a[1234];
ld angle1, angle2;
pair<ld, ld> A[1234];
vector<ld> ans, v, bisect;

ld get_angle(int x, int y)
{
    ld angle = atan2(y,x) * 180 / PI;
    if (angle < 0)
    {
        angle += 360;
    }
    return angle;
}

bool intersect(ld x, ld y, ld z)
{
    if(y-x > 180)
        return (z<x+eps || z>y-eps);
    return (x<z+eps && z-eps<y);
}

int main()
{
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);

    cin>>n;

    for(i=1; i<=n; ++i)
    {
        cin>>X1>>Y1>>X2>>Y2;
        angle1 = get_angle(X1, Y1);
        angle2 = get_angle(X2, Y2);
        if(angle1 > angle2)
            swap(angle1, angle2);
        A[i] = {angle1, angle2};
        v.push_back(angle1);
        v.push_back(angle2);
    }

    sort(v.begin(), v.end());

    m = v.size();
    for(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(i=1; i<=n; ++i)
    {
        for(j=1; j<=m; ++j)
            a[i][j] = intersect(A[i].first, A[i].second, bisect[j-1]);
        cin>>xr;
        a[i][m+1] = xr;
    }

    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=m+1; ++j)
            if(a[i][j])
                break;

        if(j==m+2)
            continue;
        p[i] = j;

        for(j=1; j<=n; ++j)
            if(i!=j && a[j][p[i]])
                a[j] ^= a[i];
    }

    for(i=1; i<=n; ++i)
        if(p[i] && a[i][m+1])
            ans.push_back(bisect[p[i]-1]);

    cout<<(int) ans.size() << "\n";
    for(auto x : ans)
    {
        cout << fixed << setprecision(10) << x << "\n";

    }
    return 0;
}