Cod sursa(job #2920842)

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

using namespace std;

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

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];

long double Angle (PII P) {
    long double rads = atan2(P.second, P.first);
    long double 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 Sz;
long double Value[2*NMAX];

bitset <2*NMAX> Eq[NMAX];

void Precompute () {
    vector <long double> Ang;

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

    sort(Ang.begin(), Ang.end());

    Sz = 0;
    for (int i = 0; i < Ang.size() - 1; ++ i ) {
        if (Ang[i] != Ang[i+1])
            Value[++ Sz] = (Ang[i] + Ang[i+1]) * .5;
    }

    Value[++ Sz] = (Ang[0] + Ang[Ang.size()-1]) *.5;
    Value[Sz] += 180;

    if (Value[Sz] > 360.0) Value[Sz] -= 360.0;

    for (int i = 1; i <= N; ++ i ) {
        long double low = Angle(A[i].first);
        long double high = Angle(A[i].second);
        long double diff = high - low;

        bool state;
        f >> state;
        Eq[i][Sz+1] = state;

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

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

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

        if (j == Sz+2) continue;

        if (j == Sz+1) {
            cerr << "Wtf ? ";
            exit(0);
        }

        P[i] = j;

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

bool used[NMAX];
void Solve () {
    vector <int> ans;
    for (int i = 1; i <= N; ++ i )
        if (P[i] != 0 && Eq[i][Sz+1] == 1) used[P[i]] = true;

    for (int i = 1; i <= Sz; ++ i )
        if (used[i]) ans.push_back(i);
    g << ans.size() << '\n';
    g << setprecision(6) << fixed;
    for (auto it : ans)
        g << Value[it] << '\n';
}

int main () {
    Read();
    Precompute();
    Gauss();
    Solve();

    return 0;
}