Cod sursa(job #3328035)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 5 decembrie 2025 23:30:59
Problema Laser Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("laser.in");
ofstream fout("laser.out");
typedef double Unghi;
const double PI = acos(-1);
const double ERROARE = 0.00001;
const int MAX = 520;

Unghi ung[2 * MAX];
Unghi v1[MAX], v2[MAX];
int n, i, j, nr, poz[MAX];
bitset<2 * MAX> flip[MAX];

vector<Unghi> bis;
vector<Unghi> rasp;

static inline Unghi Modul(Unghi a) {
    return (a < 0 ? a + 2 * PI : a);
}

static inline Unghi GetUnghi(int x, int y) {
    return Modul(atan2(y, x));
}

static inline Unghi Bisectoare(Unghi a, Unghi b) {
    return (a + b) / 2.0;
}

static inline bool Intersecteaza(Unghi u1, Unghi u2, Unghi u3) {
    if(u2 - u1 > PI) return (u3 - u1 < ERROARE || u2 - u3 < ERROARE);
                     return (u1 - u3 < ERROARE && u3 - u2 < ERROARE);
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n;
    for(i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;

        Unghi u1 = GetUnghi(x1, y1);
        Unghi u2 = GetUnghi(x2, y2);

        if(u1 > u2) swap(u1, u2);
        ung[++nr] = u1;
        ung[++nr] = u2;
        v1[i] = u1;
        v2[i] = u2;
    }

    sort(ung + 1, ung + nr + 1);

    for(i = 1; i + 1 <= nr; i++) {
        bis.push_back(Bisectoare(ung[i], ung[i + 1]));
    }

    bis.push_back((ung[1] + ung[nr] + 2 * PI) / 2);

    if(bis.back() > 2 * PI) bis.back() -= 2 * PI;

    for(i = 1; i <= n; i++) {
        for(j = 0; j < nr; j++) {
            flip[i][j] = Intersecteaza(v1[i], v2[i], bis[j]);
        }

        bool setCur;
        fin >> setCur;
        flip[i][nr] = setCur;
    }

    for(i = 1; i <= n; i++) poz[i] = -1;
    for(i = 1; i <= n; i++) {
        for(j = 0; j <= nr; j++) {
            if(flip[i][j]) break;
        }

        if(j == nr + 1) continue;

        poz[i] = j;

        for(j = 1; j <= n; j++) {
            if(i != j && flip[j][poz[i]]) flip[j] ^= flip[i];
        }

    }
    for(i = 1; i <= n; i++) {
        if(poz[i] != -1 && flip[i][nr] == 1) {
            rasp.push_back(bis[poz[i]]);
        }
    }

    fout << rasp.size() << "\n";
    fout << setprecision(6) << fixed;
    for(Unghi cur : rasp) fout << cur / PI * 180.0 << "\n";

    return 0;
}