Cod sursa(job #1675728)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 5 aprilie 2016 15:22:54
Problema Laser Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.61 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>
#define PI 3.14159265359
#define EPS 0.00001
#define MAXN 512
#define INF 1000000000.0
struct punct{
    double x, y;
}p[4*MAXN+9];
struct segment{
    double x, y, a, b;
}v[MAXN];
std::bitset<MAXN+1>a[4*MAXN+10];
int n, u, r[4*MAXN+9];
inline double myabs(double x){
    if(x<0) return -x;
    return x;
}
inline double myatan2(int y, int x){
    double a=atan2(y, x);
    if(a<0) a+=2*PI;
    return a*180/PI;
}
bool cmp(punct a, punct b){
    return myatan2(a.y, a.x)<myatan2(b.y, b.x);
}
inline double arie(double a1, double b1, double a2, double b2, double a3, double b3){
    return a1*b2-a2*b1+a2*b3-a3*b2+a3*b1-a1*b3;
}
inline bool interior(double a1, double b1, double a2, double b2, double a3, double b3){
    return myabs(arie(a1, b1, a2, b2, a3, b3))==(myabs(arie(a1, b1, a2, b2, 0, 0))+myabs(arie(a1, b1, a3, b3, 0, 0))+myabs(arie(a2, b2, a3, b3, 0, 0)));
}
inline bool intersect(punct p, segment s){
    if((arie(0, 0, s.x, s.y, p.x, p.y)>-EPS)&&(arie(0, 0, s.a, s.b, p.x, p.y)<EPS)) return 1-interior(p.x, p.y, s.x, s.y, s.a, s.b);
    if((arie(0, 0, s.x, s.y, p.x, p.y)<EPS)&&(arie(0, 0, s.a, s.b, p.x, p.y)>-EPS)) return 1-interior(p.x, p.y, s.x, s.y, s.a, s.b);
    return 0;
}
inline void baga(int l){
    int i;
    for(i=1; i<=u; i++){
        if(intersect(p[l], v[i])){
            a[i][l]=1;
        }
    }
}
inline void gauss(){
    int i, j, aux, k, p, f;
    i=1;
    j=1;
    while((i<=u)&&(j<=n)){
        k=i;
        while((k<=u)&&(a[k][j]==0)){
            k++;
        }
        if(k<=u){
            if(i!=k){
                for(p=1; p<=n+1; p++){
                    aux=a[i][p];
                    a[i][p]=a[k][p];
                    a[k][p]=aux;
                }
            }
            for(k=i+1; k<=u; k++){
                if(a[k][j]){
                    a[k]=a[k]^a[i];
                }
            }
            i++;
            j++;
        }else{
            j++;
        }
    }
    for(i=u; i>0; i--){
        j=1;
        f=1;
        while((j<=n)&&(f)){
            if(a[i][j]){
                f=0;
                r[j]=a[i][n+1];
                for(p=j+1; p<=n; p++){
                    r[j]^=a[i][p]*r[p];
                }
            }else{
                j++;
            }
        }
    }
}
int main(){
    int i, aux, ans;
    FILE *fin, *fout;
    fin=fopen("laser.in", "r");
    fout=fopen("laser.out", "w");
    fscanf(fin, "%d", &u);
    n=0;
    for(i=1; i<=u; i++){
        fscanf(fin, "%lf%lf%lf%lf", &v[i].x, &v[i].y, &v[i].a, &v[i].b);
        n++;
        p[n].x=v[i].x;
        p[n].y=v[i].y;
        n++;
        p[n].x=v[i].a;
        p[n].y=v[i].b;
    }
    n++;
    p[n].x=0;
    p[n].y=INF;
    n++;
    p[n].x=INF;
    p[n].y=0;
    n++;
    p[n].x=0;
    p[n].y=-INF;
    n++;
    p[n].x=-INF;
    p[n].y=0;
    std::sort(p+1, p+n+1, cmp);
    for(i=1; i<n; i++){
        baga(i);
        p[i+n].x=(p[i].x+p[i+1].x)/2;
        p[i+n].y=(p[i].y+p[i+1].y)/2;
        baga(i+n);
    }
    baga(n);
    p[2*n].x=(p[2*n].x+p[1].x)/2;
    p[2*n].y=(p[2*n].y+p[1].y)/2;
    baga(2*n);
    n=2*n;
    for(i=1; i<=u; i++){
        fscanf(fin, "%d", &aux);
        a[i][n+1]=aux;
    }
    gauss();
    ans=0;
    for(i=1; i<=n; i++){
        if(r[i]){
            ans++;
        }
    }
    fprintf(fout, "%d\n", ans);
    for(i=1; i<=n; i++){
        if(r[i]){
            fprintf (fout, "%.6lf\n", myatan2(p[i].y, p[i].x));
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}