Cod sursa(job #2334922)

Utilizator refugiatBoni Daniel Stefan refugiat Data 3 februarie 2019 12:54:34
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <bits/stdc++.h>
using namespace std;
ifstream si("laser.in");
ofstream so("laser.out");
const double eps=1e-5;
const double pi=acos(-1);
const int MAXN=512;
inline double get_ang(double ang) {
    return ang*180.0/pi;
}
inline double get_slope(double s) {
    if(s<0)
        return s+2*pi;
    return s;
}

inline bool ok(double ang, pair <double, double> s) {
    if(s.first-s.second<0) {
        return s.first-ang<=0&&s.second-ang>=0;
    }
    else {
        return s.first-ang<=0||s.second-ang>=0;
    }
}
inline int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    return x1*y2+x2*y3+x3*y1-y2*x3-y3*x1-y1*x2;
}

pair<double, double> seg[MAXN];
double slope[2*MAXN], arr[2*MAXN];
bool sol[2*MAXN];
bitset<2*MAXN+1> eqs[MAXN];
int main() {
    int i, j, n;
    si>>n;
    int m=0;
    for(i=0; i<n; i++) {
        int x1, y1, x2, y2;
        si>>x1>>y1>>x2>>y2;
        double ang1=get_ang(get_slope(atan2(y1, x1))), ang2=get_ang(get_slope(atan2(y2, x2)));
        ang1*=10000;
        ang2*=10000;
        if(ccw(0, 0, x1, y1, x2, y2)>=0) {
            seg[i]={ang1, ang2};
        }
        else {
            seg[i]={ang2, ang1};
        }
        slope[m++]=ang1;
        slope[m++]=ang2;
    }
    sort(slope, slope+m);
    for(i=0; i<m; i++) {
        arr[i]=(slope[i]+slope[(i+1)%m])*0.5;
        for(j=0; j<n; j++) {
            if(ok(arr[i], seg[j])) {
                eqs[j][i]=1;
            }
        }
    }
    for(i=0; i<n; i++) {
        int x;
        si>>x;
        eqs[i][m]=x;
    }
    int l=0, c=0;
    while(l<n&&c<m) {
        i=l;
        while(i<n&&eqs[i][c]==0) {
            i++;
        }
        if(i==n) {
            c++;
        }
        else {
            swap(eqs[i], eqs[l]);
            for(i=l+1; i<n; i++) {
                if(eqs[i][c]==1)
                    eqs[i]^=eqs[l];
            }
            l++;
            c++;
        }
    }
    int cnt=0;
    for(i=n-1; i>=0; i--) {
        j=0;
        while(j<m&&eqs[i][j]==0) {
            j++;
        }
        for(int p=j+1; p<m; p++) {
            if(eqs[i][p])
                eqs[i][m]=eqs[i][m]^sol[p];
        }
        sol[j]=eqs[i][m];
        cnt+=sol[j];
    }
    so<<cnt<<'\n';
    for(i=0; i<m; i++) {
        if(sol[i])
            so<<fixed<<setprecision(6)<<arr[i]/10000<<'\n';
    }
    return 0;
}