Cod sursa(job #2920849)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 26 august 2022 13:31:01
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("laser.in");
ofstream g ("laser.out");

typedef long double LD;
typedef pair <int, int> PII;
typedef pair <PII, PII> PPIPI;
constexpr long double PI = acos(-1);
constexpr int NMAX = 520;

int N;
PPIPI A[NMAX];

LD Angle (PII P) {
    LD rads = atan2(1.0 * P.second, 1.0 * P.first);
    LD degrees = rads * 180.0 / PI;

    return degrees < 0 ? degrees + 360.0 : degrees;
}

void Read () {
    f >> N;

    for (int i = 1; i <= N; ++ i ) {
        f >> A[i].first.first >> A[i].first.second >> A[i].second.first >> A[i].second.second;

        if (Angle(A[i].first) > Angle(A[i].second))
            swap(A[i].first, A[i].second);
    }
}

int vf = 0;
LD Ang[2*NMAX+5];

int Sz = 0;
LD Value[2*NMAX+5];

void Precompute () {
    for (int i = 1; i <= N; ++ i ) {
        Ang[++vf] = Angle(A[i].first);
        Ang[++vf] = Angle(A[i].second);
    }

    sort(Ang+1, Ang+vf+1);

    vector <LD> Red;
    Red.push_back(Ang[1]);
    for (int i = 2; i <= vf; ++ i )
        if (Ang[i] != Red.back()) Red.push_back(Ang[i]);

    for (int i = 1; i < Red.size(); ++ i )
        Value[i] = (Red[i-1] + Red[i]) * .5;
    Sz = Red.size()-1;

    if (Red.size() > 1) {
        Value[Red.size()] = (Red[0] + Red.back()) * .5 + 180.0;
        if (Value[Red.size()] > 360.0) Value[Red.size()] -= 360.0;

        Sz = Red.size();
    }
}

bitset <2*NMAX> Eq[NMAX];

void Make_Equations () {
    for (int i = 1; i <= N; ++ i ) {
        LD low = Angle(A[i].first);
        LD high = Angle(A[i].second);

        LD diff = high - low;

        int state;
        f >> state;

        Eq[i][Sz+1] = state;

        for (int j = 1; j <= Sz; ++ j ) {
            Eq[i][j] = 0;
            if (diff > 180.0) {
                if (Value[j] < low || Value[j] > high)
                    Eq[i][j] = 1;
            }
            else {
                if (low <= Value[j] && Value[j] <= high)
                    Eq[i][j] = 1;
            }
        }
    }
}

void Afis () {
    for (int i = 1; i <= N; ++ i ) {
        for (int j = 1; j <= Sz+1; ++ j )
            cerr << Eq[i][j] << " ";
        cerr << '\n';
    }
}

int P[NMAX];

void Gauss () {
    //Afis();
    for (int i = 1; i <= N; ++ i ) {
        int j = 0;
        P[i] = 0;

        for (j = 1; j <= Sz + 1; ++ j )
            if (Eq[i][j]) break;

        if (j == Sz+2) continue;

        P[i] = j;

        for (int j = 1; j <= N; ++ j )
            if (i != j && Eq[j][P[i]])
                Eq[j] ^= Eq[i];
    }
}

void Write () {
    //for (int i = 1; i <= N; ++ i )
       // cerr << P[i] << " ";
    vector <int> ans;
    for (int i = 1; i <= N; ++ i ) {
        if (P[i] != 0 && Eq[i][Sz+1])
            ans.push_back(P[i]);
    }

    g << ans.size() << '\n';

    g << setprecision(6) << fixed;

    for (auto it : ans)
        g << Value[it] << '\n';
}
int main () {
    Read();
    Precompute();
    Make_Equations();
    Gauss();
    Write();

    return 0;
}