Cod sursa(job #2784469)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 16 octombrie 2021 15:31:20
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>

#define PI 3.14159265
using namespace std;

ifstream fin("laser.in");
ofstream fout("laser.out");

const int NMAX(520);
struct chestie{
    int x1, y1, x2, y2;
    double u1, u2;
}v[NMAX];
double vec[2 * NMAX], bisec[2 * NMAX];
int n, sol[2 * NMAX];
bitset<1024> mat[NMAX];

inline double conv(double ungh){
    if(ungh >= 0.000000000001)
        return ungh;
    return 360 - abs(ungh);
}

inline void Gauss(){
    for(int i = 1; i <= n; ++i){
        int j = 1;
        while(j <= 2 * n && mat[i][j] == 0)
            ++j;
        if(j == 2 * n + 1)
            continue;
        sol[i] = j;
        for(int k = 1; k <= n; ++k)
            if(k != i && mat[k][j])
                mat[k] ^= mat[j];
    }
}

int main()
{
    fin >> n;

    int nr = 0;
    for(int i = 1; i <= n; ++i){
        fin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2;
        vec[++nr] = conv(atan2(v[i].y1, v[i].x1) * 180 / PI);
        v[i].u1 = vec[nr];
        vec[++nr] = conv(atan2(v[i].y2, v[i].x2) * 180 / PI);
        v[i].u2 = vec[nr];
        if(v[i].u1 > v[i].u2)
            swap(v[i].u1, v[i].u2);
    }

    sort(vec + 1, vec + 2 * n + 1);

    int cnt = 0;
    for(int i = 2; i <= 2 * n; ++i)
        bisec[++cnt] = (vec[i] + vec[i - 1]) / 2.0;
    bisec[++cnt] = (360 + vec[1] + vec[2 * n]) / 2.0;
    if(bisec[cnt] >= 360)
        bisec[cnt] -= 360;
    sort(bisec + 1, bisec + 2 * n + 1);

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= 2 * n; ++j)
            if((v[i].u2 - v[i].u1 <= 180 && v[i].u1 <= bisec[j] && bisec[j] <= v[i].u2) || (v[i].u2 - v[i].u1 > 180 && (bisec[j] < v[i].u1 || v[i].u2 < bisec[j])))
                mat[i][j] = 1;
    for(int i = 1; i <= n; ++i){
        int val;
        fin >> val;
        mat[i][2 * n + 1] = val;
    }

    Gauss();

    vector<double> rez;
    for(int i = 1; i <= 2 * n; ++i)
        if(sol[i] != 0)
            rez.push_back(bisec[i]);

    fout << rez.size() << '\n';
    for(auto it: rez)
        fout << fixed << setprecision(7) << it << '\n';
    return 0;
}