Cod sursa(job #801891)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 25 octombrie 2012 13:18:20
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <cstdio>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <bitset>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;

const int MaxN = 550;
const int MaxP = 1100;

pii P[MaxP];
int N, M, Sol[MaxP];
bitset<MaxP> A[MaxN];

inline int Sign(int a, int b, int c, pii p) {
    if (a*p.x+b*p.y+c < 0)
        return -1;
    if (a*p.x+b*p.y+c > 0)
        return 1;
    return 0;
}

inline bool Intersect(pii p1, pii p2, int a, int b, int c) {
    return Sign(a, b, c, p1)*Sign(a, b, c, p2) <= 0;
}

void BuildSystem() {
    for (int i = 0; i < M; ++i) {
        int a = P[i].y, b = -P[i].x, c = 0;
        for (int j = 0; j < N; ++j) {
            int a2 = P[j].y-P[j+N].y, b2 = P[j+N].x-P[j].x, c2 = 0;
            if (Intersect(P[j], P[j+N], a, b, c) && Sign(a2, b2, c2, P[j]) == Sign(a2, b2, c2, P[i]))
                A[j][i] = 1;
        }
    }
}

void Gauss() {
    int i = 0, j = 0;
    while (i < N && j < M) {
        int k;
        for (k = i; k < N && !A[i][j]; ++k);
        if (k == N) {
            ++j; continue;
        }
        swap(A[i], A[k]);
        for (k = 0; k < N; ++k)
            if (i != k && A[k][j])
                A[k] ^= A[i];
        ++i, ++j;
    }
}

void BuildSol() {
    for (int i = N-1, j; i >= 0; --i) {
        for (j = 0; j <= M && !A[i][j]; ++j);
        for (int k = j+1; k < M; ++k)
            if (A[i][k])
                A[i][M] = A[i][M]^Sol[k];
        if (j < M)
            Sol[j] = A[i][M];
    }
}

void Solve() {
    BuildSystem();
    Gauss();
    BuildSol();
}

void Read() {
    assert(freopen("laser.in", "r", stdin));
    assert(scanf("%d", &N) == 1); M = 2*N;
    for (int i = 0; i < N; ++i)
        assert(scanf("%d %d %d %d", &P[i].x, &P[i].y, &P[i+N].x, &P[i+N].y) == 4);
    for (int i = 0; i < N; ++i) {
        int C; assert(scanf("%d", &C) == 1);
        A[i][M] = C;
    }
}

void Print() {
    assert(freopen("laser.out", "w", stdout));
    int n = 0;
    for (int i = 0; i < M; ++i)
        n += Sol[i];
    printf("%d\n", n);
    for (int i = 0; i < M; ++i) {
        if (Sol[i]) {
            double Alpha = 180.0/acos(-1)*atan2(P[i].y, P[i].x);
            printf("%.8lf\n", Alpha <= 0.0 ? 360.0+Alpha : Alpha);
        }
    }
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}