Cod sursa(job #1239562)

Utilizator teoionescuIonescu Teodor teoionescu Data 9 octombrie 2014 11:34:33
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<cmath>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream in("laser.in");
ofstream out("laser.out");
const int Nmax = 520;
const double PI = 2.0*asin(1);
struct point{
    int x,y,ind;
    point(){}
    point(int _x,int _y,int _ind){x=_x,y=_y,ind=_ind;}
} v[3*Nmax];
int cp(point A,point B,point C){return A.x*B.y - A.y*B.x + B.x*C.y - B.y*C.x + C.x*A.y - C.y*A.x;}
struct cmpA{inline bool operator()(const point &a,const point &b){return a.y<b.y;}};
struct cmpB{inline bool operator()(const point &a,const point &b){return cp(point(0,0,0),a,b) < 0;}};
bitset<Nmax> B,S[3*Nmax];
bitset<3*Nmax> V[Nmax]; //SIZE 2*Nmax
int N,K,n,m,To[3*Nmax],Tip[3*Nmax];
int srch(int ind){
    for(int i=1;i<=m;i++) if(V[ind][i]) return i;
    return m+2;
}
double angle(point A){
    double d=sqrt( A.x*A.x + A.y*A.y );
    double ung = abs( acos( double(A.x)/d ) );
    if(A.y<0) ung += 2*(PI-ung);
    return ung;
}
int main(){
    in>>N;
    for(int i=1;i<=N;i++){
        int x,y;
        in>>x>>y;
        v[i]=point(x,y,i);
        in>>x>>y;
        v[N+i]=point(x,y,i);
    }
    sort(v+1,v+2*N+1,cmpA());
    int sep=2*N+1;
    for(int i=1;i<=2*N;i++) if(sep>2*N && v[i].y>0) sep=i;
    sort(v+1,v+sep,cmpB());
    sort(v+sep,v+2*N+1,cmpB());
    v[2*N+1]=v[1];
    for(int i=1;i<=2*N;i++){
        if(!Tip[v[i].ind]) Tip[v[i].ind]=i;
        else{
            To[i]=Tip[v[i].ind];
            To[Tip[v[i].ind]]=i;
        }
    }
    for(int i=1;i<=2*N;i++) Tip[i]=( cp(point(0,0,0),v[i],v[To[i]])<0 );
    for(int i=1;i<=2*N;i++) B[v[i].ind]=Tip[i];
    for(int i=1;i<=2*N;i++) B[v[i].ind]=Tip[i], S[i]=B;
    for(int i=1;i<=N;i++){
        int x;
        in>>x;
        S[2*N+1][i]=x;
    }
    n=N,m=2*N;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=2*N;j++) V[i][j]=S[j][i];
        V[i][m+1]=S[2*N+1][i];
    }
    int pos[Nmax],ans[3*Nmax];
    memset(ans,0,sizeof(ans));
    for(int row=1;row<=n;row++){
        int ind=row;
        pos[row]=srch(row);
        for(int i=row;i<=n;i++){
            int p=srch(i);
            if(p<pos[row]) pos[row]=p,ind=i;
        }
        swap(V[row],V[ind]);
        for(int i=row+1;i<=n;i++) if(V[i][pos[row]]) V[i]^=V[row];
    }
    for(int i=1;i<=n;i++){
        int s=0;
        for(int j=pos[i]+1;j<=m;j++) s^=V[i][j]*ans[j];
        ans[pos[i]]=s^V[i][m+1];
    }
    for(int i=1;i<=m;i++) ans[0]+=ans[i];
    out<<ans[0]<<'\n';
    for(int i=1;i<=2*N;i++){
        if(ans[i]){
            double angA = angle(v[i]);
            double angB = angle(v[i+1]);
            angA=(angA+angB)/2.;
            angA=angA/(2*PI)*360.;
            out.precision(6);
            out<<fixed<<angA<<'\n';
        }
    }
    return 0;
}