Cod sursa(job #2465885)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 30 septembrie 2019 23:24:58
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <bits/stdc++.h>

using namespace std;

#define double long double

const double PI = acos (-1), EPS = 1e-10;

const int N = 512;
#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 (x, y);
    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 (6) << it / PI * 180 << "\n"; /// din radiani in grade

    return 0;
}