Cod sursa(job #1526688)

Utilizator lflorin29Florin Laiu lflorin29 Data 17 noiembrie 2015 00:54:56
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <bits/stdc++.h>

using namespace std;

class segm {
    public:
    int x1, y1, x2, y2;
    segm() {};
    segm(int _x1, int _y1, int _x2, int _y2) : x1(_x1), y1(_y1), x2(_x2), y2(_y2) {};

    const pair<double, double>angles() const{
            const auto alpha = [&] (int p1, int p2) {
            double ret = 180.0 * atan2(1.0 * p2, 1.0 * p1) / (2 * acos(0));
            if(ret < 0.0)
                ret += 360.0;
            return ret;
        };

        pair<double, double>value(alpha(x2, y2), alpha(x1, y1));
        return value;
    }
};

const int bitset_size = 1050;
const double EPS = 1e-10;

int main() {
    ifstream cin("laser.in");
    ofstream cout("laser.out");

    int N; cin >> N;
    vector<segm>A(N);

    for(int i = 0; i < N; ++i)
       cin >> A[i].x1 >> A[i].y1 >> A[i].x2 >> A[i].y2;

    vector<double>bef;
    for(int i = 0; i < N; ++i) {
        const pair<double, double> how = A[i].angles();
        bef.emplace_back(how.first), bef.emplace_back(how.second);
    }

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

    vector<double>angles(bef);
    for(int i = 0; i < (int)angles.size() - 1; ++i) {
        angles[i] = (bef[i] + bef[i + 1]) / 2;
        if(angles[i] >= 360.0)
            angles[i] -= 360.0;
    }

    vector<bitset<bitset_size>>eq(N);
    for(int i = 0; i < N; ++i) {
        int value; cin >> value;
        eq[i][(int)angles.size()] = value;
    }

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < (int)angles.size(); ++j) {
            pair<double, double> alpha = A[i].angles();
            if(alpha.first > alpha.second + EPS)
                swap(alpha.first, alpha.second);
            if(alpha.second - alpha.first - EPS < 180.0)
                eq[i][j] = (alpha.first - EPS <= angles[j] && alpha.second + EPS >= angles[j]);
            else
                eq[i][j] = (alpha.second - EPS <= angles[j] || alpha.first + EPS >= angles[j]);
        }

    for(int i = 0, j = 0; i < N && j < (int)angles.size(); ++i, ++j) {
        int alpha = i;

        for(int k = i; k < N; ++k)
            if(eq[k][j] > eq[alpha][j])
               alpha = k;

        if(eq[alpha][j] == 0) {
           --i;
           continue;
        }

        swap(eq[i], eq[alpha]);
        for(int k = i + 1; k < N; ++k)
            if(eq[k][j])
               eq[k] ^= eq[i];
    }

    vector<bool>nec((int)angles.size());
    int ans = 0;

    for(int i = N - 1; i >= 0; --i)
        for(int j = 0; j < (int)angles.size(); ++j)
            if(eq[i][j]) {
               nec[j] = eq[i][(int)angles.size()];
               for(int k = j + 1; k < (int)angles.size(); ++k)
                  nec[j] = nec[j] ^ (nec[k] & eq[i][k]);
               ans += nec[j];
               break;
            }

    cout << ans << '\n';
    cout << setprecision(6) << fixed;
    for(int i = 0; i < (int)angles.size(); ++i)
        if(nec[i])
           cout << angles[i] << '\n';
    return 0;
}