Cod sursa(job #1252034)

Utilizator george_stelianChichirim George george_stelian Data 30 octombrie 2014 12:04:41
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define x first
#define y second

using namespace std;

const double eps=0.00000001;
double angle[1030];
pair<double,double> seg[520];
char v[520][1030],sol[1030];

double getangle(int x, int y)
{
    double a=atan2(y,x)*180.0/acos(-1);
    if(a<0.0) a+=360.0;
    return a;
}

int main()
{
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);
    int n;
    scanf("%d",&n);
    int m=2*n;
    for(int i=1;i<=n;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        seg[i].x=getangle(x1,y1);
        seg[i].y=getangle(x2,y2);
        if(seg[i].x>seg[i].y) swap(seg[i].x,seg[i].y);
        angle[i]=seg[i].x;
        angle[i+n]=seg[i].y;
    }
    for(int i=1;i<=n;i++) scanf("%d",&v[i][m+1]);
    sort(angle+1,angle+m+1);
    angle[m+1]=angle[1]+360.0;
    for(int i=1;i<=m;i++)
    {
        angle[i]=(angle[i]+angle[i+1])/2.0;
        if(angle[i]>360.0) angle[i]-=360.0;
    }
    for(int i=1;i<=n;i++)
        if(seg[i].y-seg[i].x<180.0+eps)
             for(int j=1;j<=m;j++) v[i][j]=(angle[j]>=seg[i].x-eps && angle[j]<=seg[i].y+eps);
        else for(int j=1;j<=m;j++) v[i][j]=(angle[j]<=seg[i].x+eps || angle[j]>=seg[i].y-eps);
    int i=1,j=1,q;
    while(i<=n && j<=m)
    {
        for(q=i;q<=n;q++) if(v[q][j]) break;
        if(q==n+1) {j++;continue;}
        if(q>i) swap(v[i],v[q]);
        for(q=i+1;q<=n;q++)
            if(v[q][j]) for(int k=j;k<=m+1;k++) v[q][k]^=v[i][k];
        i++;j++;
    }
    for(i=n;i;i--)
        for(j=i;j<=m;j++)
            if(v[i][j])
            {
                sol[j]=v[i][m+1];
                for(q=j+1;q<=m;q++) sol[j]^=v[i][q]&sol[q];
                break;
            }
    int nr=0;
    for(int i=1;i<=m;i++) if(sol[i]) nr++;
    printf("%d\n",nr);
    for(i=1;i<=m;i++) if(sol[i]) printf("%lf\n",angle[i]);
    return 0;
}