Cod sursa(job #2137403)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 20 februarie 2018 19:35:02
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include<fstream>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<algorithm>
#define f first
#define s second
#define PI 3.141592653589793
using namespace std;
int n, m, i, j, ii, x, nr;
bitset<1030> a[520], sol;
struct str{
    int x, y, x2, y2;
};
str v[520];
double u;
pair<int, int> w[1030], p;
ifstream fin("laser.in");
ofstream fout("laser.out");
int det(int X1, int Y1, int X2, int Y2, int X3, int Y3){
    long long a = (X2 - X1) * 1LL * (Y3 - Y1) - (X3 - X1) * 1LL * (Y2 - Y1);
    if(a < 0){
        return -1;
    }
    if(a > 0){
        return 1;
    }
    return 0;
}
int cmp(pair<int, int> a, pair<int, int> b){
    return det(0, 0, a.f, a.s, b.f, b.s) < 0;
}
int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> v[i].x >> v[i].y >> v[i].x2 >> v[i].y2;
        w[++m] = make_pair(v[i].x, v[i].y);
        w[++m] = make_pair(v[i].x2, v[i].y2);
    }
    sort(w + 1, w + m + 1, cmp);
    w[m + 1] = w[1];
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            p.f = (w[j].f + w[j + 1].f) * 10000;
            p.s = (w[j].s + w[j + 1].s) * 10000;
            if(det(0, 0, p.f, p.s, v[i].x, v[i].y) * det(0, 0, p.f, p.s, v[i].x2, v[i].y2) < 0){
                if(det(v[i].x, v[i].y, v[i].x2, v[i].y2, 0, 0) * det(v[i].x, v[i].y, v[i].x2, v[i].y2, p.f, p.s) < 0){
                    a[i][j] = 1;
                }
            }
        }
    }
    for(i = 1; i <= n; i++){
        fin>> x;
        a[i][2 * n + 1] = x;
    }
    m = n + n + 1;
    i = j = 1;
    while(i <= n && j < m){
        for(ii = i; ii <= n; ii++){
            if(a[ii][j] == 1){
                break;
            }
        }
        if(ii == n + 1){
            j++;
            continue;
        }
        if(ii != i){
            swap(a[i], a[ii]);
        }
        for(ii = i + 1; ii <= n; ii++){
            if(a[ii][j] == 1){
                a[ii] ^= a[i];
            }
        }
        i++;
        j++;
    }
    for(i = n; i >= 1; i--){
        for(j = 1; j <= m; j++){
            if(a[i][j] == 1){
                break;
            }
        }
        sol[j] = a[i][m];
        for(ii = j + 1; ii < m; ii++){
            sol[j] = sol[j] ^ (a[i][ii] * sol[ii]);
        }
        if(sol[j] == 1){
            nr++;
        }
    }
    fout<< nr <<"\n";
    for(i = 1; i < m; i++){
        if(sol[i] == 0){
            continue;
        }
        p.f = (w[i].f + w[i + 1].f) * 10000;
        p.s = (w[i].s + w[i + 1].s) * 10000;
        u = atan2(p.s * 1.0, p.f * 1.0);
        if(u < 0){
            u += 2 * PI;
        }
        u = u / PI * 180;
        fout<< setprecision(6) << fixed << u <<"\n";
    }
    return 0;
}