Cod sursa(job #740443)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 24 aprilie 2012 19:58:16
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bitset>

using namespace std;

#define maxn 1550
#define PI 3.14159265

int n, nsol, m, ns, f[maxn], c[maxn];
double a[maxn], sol[maxn];
struct neon
{
    pair<int, int> p1, p2;
    double u1, u2;
} v[maxn];
pair<double, int> q[maxn];
bitset<maxn> g[maxn];

int det(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3)
{
    int d = p1.first*p2.second + p2.first*p3.second + p3.first*p1.second
          - p2.first*p1.second - p3.first*p2.second - p1.first*p3.second;

    if(d>0)
        return 1;
    if(d<0)
        return -1;
    return 0;
}

void new_shot(double u)
{
    ++ns;
    a[ns]=u*180/PI;
    if(a[ns]<0)
        a[ns]+=360;
    if(a[ns]>360)
        a[ns]-=360;

    for(int i=1; i<=n; ++i)
        g[i][ns]=f[i];
}

void build_shots()
{
    int nq=0;

    for(int i=1; i<=n; ++i)
    {
        if(det(make_pair(0, 0), v[i].p1, v[i].p2)==-1)
            swap(v[i].p1, v[i].p2);

        v[i].u1=atan2(1.0*v[i].p1.second, 1.0*v[i].p1.first);
        v[i].u2=atan2(1.0*v[i].p2.second, 1.0*v[i].p2.first);

        if(v[i].u1<0)
            v[i].u1+=2*PI;
        if(v[i].u2<0)
            v[i].u2+=2*PI;

        if(v[i].u2<v[i].u1)
            f[i]=1;

        q[++nq]=make_pair(v[i].u1, i);
        q[++nq]=make_pair(v[i].u2, i);
    }

    sort(q+1, q+nq+1);

    for(int i=1; i<=nq; ++i)
    {
        if(i!=1)
            new_shot((q[i].first+q[i-1].first)/2);
        f[q[i].second]=1-f[q[i].second];
    }
    new_shot((q[1].first+q[nq].first-2*PI)/2);

    for(int i=1; i<=n; ++i)
        g[i][ns+1]=c[i];
}

void solve()
{
    int i=1, j=0, l;

    while(i<=n && j<ns)
    {
        for(l=i; l<=n; ++l)
            if(g[l][j]!=0)
                break;

        if(l==n+1)
        {
            ++j;
            continue;
        }

        if(l!=i)
            swap(g[l], g[i]);

        for(int u=1; u<=n; ++u)
        {
            if(u==i)
                continue;
            if(g[u][j]==1)
                g[u]^=g[i];
        }

        ++i; ++j;
    }

    for(int i=1; i<=n; ++i)
    {
        if(g[i][ns+1]==0)
            continue;
        for(int j=1; j<=ns; ++j)
            if(g[i][j]==1)
            {
                sol[++nsol]=a[j];
                break;
            }
    }
}


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

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%d%d%d%d", &v[i].p1.first, &v[i].p1.second, &v[i].p2.first, &v[i].p2.second);
    for(int i=1; i<=n; ++i)
        scanf("%d", &c[i]);

    build_shots();
    solve();

    printf("%d\n", nsol);
    for(int i=1; i<=nsol; ++i)
        printf("%.6lf\n", sol[i]);

    return 0;
}