Cod sursa(job #2266373)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 22 octombrie 2018 16:55:38
Problema Laser Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-5;
const double pi = acos(-1);
const int MAXN = 512;

inline double get_ang(double ang) {
    return ang * 180.0 / pi;
}

inline double get_slope(double s) {
    if(s < 0)
        return s + 2 * pi;
    return s;
}

inline bool ok(double ang, pair <double, double> s) {
    if(s.first - s.second < 0) {
        return s.first - ang <= 0 && s.second - ang >= 0;
    }
    else {
        return s.first - ang <= 0 || s.second - ang >= 0;
    }
}

inline int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    return x1 * y2 + x2 * y3 + x3 * y1 - y2 * x3 - y3 * x1 - y1 * x2;
}

pair <double, double> seg[MAXN];
double slope[2 * MAXN], arr[2 * MAXN];
bool sol[2 * MAXN];
bitset < MAXN > eqs[2 * MAXN + 1];

int main() {
    ifstream cin("laser.in");
    ofstream cout("laser.out");
    int i, j, n;
    ios::sync_with_stdio(false);
    cin >> n;
    int m = 0;
    for(i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        double ang1 = get_ang(get_slope(atan2(y1, x1))), ang2 = get_ang(get_slope(atan2(y2, x2)));
        ang1 *= 1e4;
        ang2 *= 1e4;
        if(ccw(0, 0, x1, y1, x2, y2) >= 0) {
            seg[i] = {ang1, ang2};
        }
        else {
            seg[i] = {ang2, ang1};
        }
        slope[m++] = ang1;
        slope[m++] = ang2;
    }
    sort(slope, slope + m);
    for(i = 0; i < m; i++) {
        arr[i] = (slope[i] + slope[(i + 1) % m]) * 0.5;
        for(j = 0; j < n; j++) {
            if(ok(arr[i], seg[j])) {
                eqs[j][i] = 1;
            }
        }
    }
    for(i = 0; i < n; i++) {
        int x;
        cin >> x;
        eqs[i][m] = x;
    }
    int l = 0, c = 0;
    while(l < n && c < m) {
        i = l;
        while(i < n && eqs[i][c] == 0) {
            i++;
        }
        if(i == n) {
            c++;
        }
        else {
            swap(eqs[i], eqs[l]);
            for(i = l + 1; i < n; i++) {
                if(eqs[i][c] == 1)
                    eqs[i] ^= eqs[l];
            }
            l++;
            c++;
        }
    }
    int cnt = 0;
    for(i = n - 1; i >= 0; i--) {
        j = 0;
        while(j < m && eqs[i][j] == 0) {
            j++;
        }
        for(int p = j + 1; p < m; p++) {
            if(eqs[i][p])
                eqs[i][m] = eqs[i][m] ^ sol[p];
        }
        sol[j] = eqs[i][m];
        cnt += sol[j];
    }
    cout << cnt << "\n";
    for(i = 0; i < m; i++) {
        if(sol[i])
            cout << fixed << setprecision(6) << arr[i] / 1e4 << "\n";
    }
    cin.close();
    cout.close();
    return 0;
}