Cod sursa(job #2137357)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 20 februarie 2018 19:06:29
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include<fstream>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<iostream>
#define PI 3.141592653589793
#define eps 0.000001
using namespace std;
int n, m, i, j, ii, x, nr, d1, d2;
bitset<1025> a[520], sol;
struct str{
    int x, y, x2, y2;
};
str v[520];
double u;
ifstream fin("laser.in");
ofstream fout("laser.out");
int det(int X1, int Y1, int X2, int Y2, int X3, int Y3){
    int a = (X2 - X1) * (Y3 - Y1) - (X3 - X1) * (Y2 - Y1);
    if(a < 0){
        return -1;
    }
    if(a > 0){
        return 1;
    }
    return 0;
}
int intersect(int X1, int Y1, int X2, int Y2, int X3, int Y3){
    double u1, u2, u3;
    u1 = atan2(Y1 * 1.0, X1 * 1.0);
    if(u1 < 0){
        u1 += 2 * PI;
    }
    u2 = atan2(Y2 * 1.0, X2 * 1.0);
    if(u2 < 0){
        u2 += 2 * PI;
    }
    u3 = atan2(Y3 * 1.0, X3 * 1.0);
    if(u3 < 0){
        u3 += 2 * PI;
    }
    if(u1 > u2){
        swap(u1, u2);
    }
    if(u1 - u3 > eps || u3 - u2 > eps){
        return 0;
    }
    return 1;
}
int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> v[i].x >> v[i].y >> v[i].x2 >> v[i].y2;
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            if(det(0, 0, v[j].x, v[j].y, v[i].x, v[i].y) * det(0, 0, v[j].x, v[j].y, v[i].x2, v[i].y2) <= 0){
                if(intersect(v[i].x, v[i].y, v[i].x2, v[i].y2, v[j].x, v[j].y)){
                    a[i][2 * j - 1] = 1;
                }
            }
            if(det(0, 0, v[j].x2, v[j].y2, v[i].x, v[i].y) * det(0, 0, v[j].x2, v[j].y2, v[i].x2, v[i].y2) <= 0){
                if(intersect(v[i].x, v[i].y, v[i].x2, v[i].y2, v[j].x2, v[j].y2)){
                    a[i][2 * 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){
            i++;
            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;
        }
        if(i % 2 == 1){
            u = atan2(v[i / 2 + 1].y * 1.0, v[i / 2 + 1].x * 1.0);
        }
        else{
            u = atan2(v[i / 2].y2 * 1.0, v[i / 2].x2 * 1.0);
        }
        if(u < 0){
            u += 2 * PI;
        }
        u = u / PI * 180;
        fout<< setprecision(6) << fixed << u <<"\n";
    }
    return 0;
}