Cod sursa(job #2466280)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 1 octombrie 2019 20:31:14
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <bits/stdc++.h>



using namespace std;



//#define double long double



const double PI = 3.14159265358979323846264338327950288, EPS = 1e-10;



const int N = 1300;

#define pb push_back

int p[1 + N];

pair <double, double> a[1 + N];



int n;



double unghi (double x, double y) {

    double ans = atan2 (y, x);

    if (ans < 0) ans += 2 * PI;

    return ans;

}



bool inside (pair <double, double> p, double x) {

    if (p.second - p.first > PI)

        return (x < p.first + EPS) || (x > p.second - EPS);

    return (x - p.first > -EPS) && (p.second - x > -EPS);

}



bitset <1 + N + 1> sistem[1 + N + 1];



int main() {

    freopen ("laser.in", "r", stdin);

    freopen ("laser.out", "w", stdout);



    ios::sync_with_stdio (false);

    cin.tie (0); cout.tie (0);



    cin >> n;

    vector <double> angles;

    for (int i = 1; i <= n; i++) {

        int x1, y1, x2, y2;

        cin >> x1 >> y1 >> x2 >> y2;

        double l, r;

        l = unghi (x1, y1);

        r = unghi (x2, y2);

        if (l - r > EPS)

            swap (l, r);

        /// doar intervalele pe cadran ne intereseaza

        a[i] = {l, r};

        angles.pb (l); angles.pb (r);

    }



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



    int m = angles.size ();

    vector <double> shots;

    for (int i = 0; i + 1 < angles.size (); i++)

        shots.pb ((angles[i] + angles[i + 1]) / 2); /// tragem pe mijloc ca de ce nu

    shots.pb ((angles[0] + angles[m - 1] + 2 * PI) / 2);

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



    for (int i = 1; i <= n; i++)  /// cream sistemul

        for (int j = 1; j <= m; j++)

            sistem[i][j] = inside (a[i], shots[j - 1]);

    for (int i = 1; i <= n; i++) {

        int x;

        cin >> x;

        sistem[i][m + 1] = x;

    }



    /// rezolvam sistemul

    for (int i = 1; i <= n; i++) {

        int j = 1;

        while (j <= m + 1 && !sistem[i][j])

            j++;

        if (j > m + 1)  /// libera

            continue;



        p[i] = j;

        for (int k = 1; k <= n; k++)

            if (i != k && sistem[k][p[i]])

                sistem[k] ^= sistem[i]; /// le scadem pe biti cea ce e tot xor

    }



    vector <double> ans;

    for (int i = 1; i <= n; i++)

        if (p[i] && sistem[i][m + 1]) /// in a[i][m + 1] avem daca tragem sau nu

            ans.pb (shots[p[i] - 1]);



    cout << ans.size () << "\n";

    for (auto it : ans)

        cout << fixed << setprecision (8) << it / PI * 180 << "\n"; /// din radiani in grade



    return 0;

}