Cod sursa(job #37396)

Utilizator dominoMircea Pasoi domino Data 24 martie 2007 23:35:11
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <bitset>

using namespace std;

#define MAX_N 512
#define FIN "laser.in"
#define FOUT "laser.out"
#define EPS 1e-7
#define abs(x) ((x) < 0.0 ? -(x) : (x))

int N, X1[MAX_N], Y1[MAX_N], X2[MAX_N], Y2[MAX_N], T[MAX_N<<2], U[MAX_N<<2], nv, nv2, Res;
double V[MAX_N<<2], V2[MAX_N<<2], ang[MAX_N][2];
bitset <MAX_N<<2> A[MAX_N];

inline bool cmp(double a, double b) { return a < b-EPS; }
inline bool eq(double a, double b) { return abs(a-b) < EPS; }
inline int between(double a, double b, double c) { return a < b+EPS && b < c+EPS; }

inline double angle(double x, double y)
{
    double t;

    t = atan2(y, x);
    if (t < 0.0) t += 2.0*M_PI;
    return t;
}

inline double fix(double ang)
{
    if (ang+EPS < 0.0) ang += 2.0*M_PI;
    if (ang-EPS > 2.0*M_PI) ang -= 2.0*M_PI;
    return ang;
}


int main(void)
{
    int i, j, k, x;
    double a, b;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &N);
    for (i = 0; i < N; i++)
    {
        scanf("%d %d %d %d", X1+i, Y1+i, X2+i, Y2+i);
        a = angle(X1[i], Y1[i]); b = angle(X2[i], Y2[i]);
        if (cmp(b, a)) swap(a, b);
        V[nv++] = a; V[nv++] = b;
        if (cmp(M_PI, b-a)) 
        {
            V[nv++] = 2.0*M_PI+a;
            V[nv++] = b-2.0*M_PI;
        }
        ang[i][0] = a; ang[i][1] = b;

    }

    sort(V, V+nv, cmp);
    for (i = 0; i+1 < nv; i++)
        V2[nv2++] = fix((V[i]+2.0*V[i+1])/3.0);
    sort(V2, V2+nv2, cmp);
    nv2 = unique(V2, V2+nv2, eq)-V2;
    for (i = 0; i < N; i++)
    {
        scanf("%d", &x);
        A[i][nv2] = x;
        for (j = 0; j < nv2; j++)
            if (cmp(M_PI, ang[i][1]-ang[i][0]))
                A[i][j] = between(0.0, V2[j], ang[i][0]) || between(ang[i][1], V2[j], 2.0*M_PI);
            else
                A[i][j] = between(ang[i][0], V2[j], ang[i][1]);
    }

    for (k = x = 0; k < nv2; k++)
    {
        for (i = x; i < N; i++)
            if (A[i][k]) break;
        if (i == N) { T[k] = -1; continue; }
        swap(A[i], A[x]);
        for (i = x+1; i < N; i++)
            if (A[i][k]) A[i] ^= A[x];
        T[k] = x++;
    }
    for (k = nv2-1; k >= 0; k--)
    {
        if (T[k] == -1) { U[k] = 0; continue; }
        U[k] = A[T[k]][nv2];
        for (i = k+1; i < nv2; i++)
            U[k] ^= A[T[k]][i]&U[i];
        if (U[k]) Res++;
    }

    printf("%d\n", Res);
    for (i = 0; i < nv2; i++)
        if (U[i]) printf("%.6f\n", V2[i]/M_PI*180.0);

    return 0;
}