Cod sursa(job #2266199)

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

using namespace std;

const long double pi = acos(-1);
const int MAXN = 512;

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

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

pair <long double, long double> slope[MAXN + 1];
bitset < MAXN + 1 > eqs[2 * MAXN + 5];

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

bool sol[2 * MAXN + 1];

int main() {
    ifstream cin("laser.in");
    ofstream cout("laser.out");
    int i, j, n;
    ios::sync_with_stdio(false);
    cin >> n;
    for(i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(ccw(0, 0, x1, y1, x2, y2) >= 0) {
            slope[i] = {get_slope(atan2(y1, x1)), get_slope(atan2(y2, x2))};
        }
        else {
            slope[i] = {get_slope(atan2(y2, x2)), get_slope(atan2(y1, x1))};
        }
    }
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            if(ok(slope[i].first, slope[j])) {
                eqs[j][i] = 1;
            }
            if(ok(slope[i].second, slope[j])) {
                eqs[j][i + n] = 1;
            }
        }
    }
    for(i = 1; i <= n; i++) {
        int x;
        cin >> x;
        eqs[i][2 * n + 1] = x;
    }
    int l = 1, c = 1;
    while(l <= n && c <= 2 * n) {
        i = l;
        while(i <= n && eqs[i][c] == 0) {
            i++;
        }
        if(i == n + 1) {
            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; i >= 1; i--) {
        j = 1;
        while(j <= 2 * n && eqs[i][j] == 0) {
            j++;
        }
        for(int p = j + 1; p <= 2 * n; p++) {
            if(eqs[i][p])
                eqs[i][2 * n + 1] = eqs[i][2 * n + 1] ^ sol[p];
        }
        sol[j] = eqs[i][2 * n + 1];
        cnt += sol[j];
    }
    cout << cnt << "\n";
    for(i = 1; i <= n; i++) {
        if(sol[i]) {
            cout << fixed << setprecision(6) << get_ang(slope[i].first) << "\n";
        }
        if(sol[i + n]) {
            cout << fixed << setprecision(6) << get_ang(slope[i].second) << "\n";
        }
    }
    cin.close();
    cout.close();
    return 0;
}