Cod sursa(job #1694954)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 26 aprilie 2016 12:38:51
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <bitset>
using namespace std;
const int NMAX = 553;
const int LMAX = 2055;
const double MIN_ANGLE = 0;
const double MAX_ANGLE = 360.0;
const double EPS = 1e-6;

struct pt {
    double x, y;
};

struct segment {
    pt a, b;
    double fromAngle, toAngle;
};

int N, M, state[NMAX];
segment A[NMAX];
double candidates[LMAX];
bitset<LMAX> G[NMAX], res;

inline double angle(pt& p) {
    double atanV = atan2(p.y, p.x);
    atanV = atanV >= 0 ? atanV : (2 * M_PI + atanV);
    return atanV * MAX_ANGLE / (2 * M_PI); 
}

void read() {
    scanf("%d", &N);
    double x1, y1, x2, y2;
    for (int i = 1; i <= N; i++) {
        scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
        A[i] = {{x1, y1}, {x2, y2}};
        A[i].fromAngle = angle(A[i].a);
        A[i].toAngle = angle(A[i].b);
        if (A[i].fromAngle > A[i].toAngle) {
            swap(A[i].fromAngle, A[i].toAngle);
        }
    }

    for (int i = 1; i <= N; i++) {
        scanf("%d", &state[i]);
    }
}

void prepare() {
    vector<double> endPoints;
    for (int i = 1; i <= N; i++) {
        endPoints.push_back(A[i].fromAngle + EPS);
        endPoints.push_back(A[i].toAngle - EPS);
    }
    endPoints.push_back(MIN_ANGLE);
    endPoints.push_back(MAX_ANGLE);

    sort(endPoints.begin(), endPoints.end());
    for (size_t i = 0; i < endPoints.size() - 1; i++) {
        candidates[++M] = (endPoints[i] + endPoints[i + 1]) / 2;
    }
    sort(candidates + 1, candidates + M + 1);

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (A[i].toAngle - A[i].fromAngle <= 180.0 + EPS) {
                G[i][j] = A[i].fromAngle - EPS <= candidates[j] &&
                    candidates[j] <= A[i].toAngle + EPS;
            } else {
                G[i][j] = A[i].toAngle - EPS <= candidates[j] ||
                    A[i].fromAngle + EPS >= candidates[j];
            }
        }
        G[i][M + 1] = state[i];
    }
}

void solve() {
    int i = 1, j = 1;
    while (i <= N) {
        if (!G[i][j]) {
            int replacementLine = -1;
            for (int k = i + 1; k <= N; k++) {
                if (G[k][j]) {
                    replacementLine = k;
                    break ;
                }
            }
            if (replacementLine == -1) {
                j++;
                continue ;
            }
            swap(G[i], G[replacementLine]);
        }

        for (int k = i + 1; k <= N; k++) {
            if (G[k][j]) {
                G[k] ^= G[i];
            }
        }
        i++; j++;
    }

    for (int i = N; i >= 1; i--) {
        if (G[i][M + 1]) {
            for (int j = 1; j <= M; j++) {
                if (G[i][j]) {
                    res[j] = G[i][M + 1];
                    for (int k = i - 1; k >= 1; k--) {
                        if (G[k][j]) {
                            G[k] ^= G[i];
                        }
                    }
                    break ;
                }
            }
        }
    }

    vector<double> sol;
    for (int i = 1; i <= M; i++) {
        if (res[i]) {
            sol.push_back(candidates[i]);
        }
    }

    printf("%d\n", (int)sol.size());
    for (auto& ang: sol) {
        printf("%.6lf\n", ang);
    }
}

int main() {
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);

    read();
    prepare();
    solve();
    return 0;
}