Cod sursa(job #801914)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 25 octombrie 2012 13:58:11
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 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;
typedef pair<double, double> pdd;

const int MaxN = 550;
const int MaxP = 1100;
const double Eps = 1e-10;

pdd Segments[MaxP];
double Alpha[MaxP];
int N, M, Sol[MaxP];
bitset<MaxP> A[MaxN];

inline double GetAlpha(int x, int y) {
    double alpha = atan2(y, x)*180.0/acos(-1);
    if (alpha < 0.0)
        alpha += 360.0;
    return alpha;
}

void BuildAlpha() {
    for (int i = 0; i < N; ++i)
        Alpha[i] = Segments[i].x, Alpha[i+N] = Segments[i].y;
    sort(Alpha, Alpha+M);
    Alpha[M] = Alpha[0];
    for (int i = 0; i < M; ++i) {
        Alpha[i] = (Alpha[i]+Alpha[i+1])/2.0;
        if (Alpha[i] > 360.0)
            Alpha[i] -= 360.0;
    }
}

void BuildSystem() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (Segments[i].y-Segments[i].x < 180.0+Eps) {
                if (Segments[i].x-Eps < Alpha[j] && Alpha[j] < Segments[i].y+Eps)
                    A[i][j] = 1;
            }
            else {
                if ((-Eps < Alpha[j] && Alpha[j] < Segments[i].x+Eps) || (Alpha[j] > 180.0-Eps && Alpha[j] > Segments[i].y))
                    A[i][j] = 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 = 0, j; i < N; ++i) {
        for (j = 0; j <= M && !A[i][j]; ++j);
        if (j < M)
            Sol[j] = A[i][M];
    }
}

void Solve() {
    BuildAlpha();
    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) {
        int x1, y1, x2, y2;
        assert(scanf("%d %d %d %d", &x1, &y1, &x2, &y2) == 4);
        Segments[i].x = GetAlpha(x1, y1), Segments[i].y = GetAlpha(x2, y2);
        if (Segments[i].x > Segments[i].y)
            swap(Segments[i].x, Segments[i].y);
    }
    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])
            printf("%.8lf\n", Alpha[i]);
}

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