Cod sursa(job #112709)

Utilizator filipbFilip Cristian Buruiana filipb Data 6 decembrie 2007 21:25:40
Problema Laser Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.34 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

#define pi 3.14159265
#define EPS 1e-16
#define x first
#define y second
#define PII pair<int, int>
#define BIT 25
#define NMax 520

int N, h, cnt;
int W[NMax][NMax << 1], A[NMax][NMax << 1], pivot[NMax], Res[NMax << 1], R[NMax];
PII P[NMax << 1];
pair< PII, PII > seg[NMax];
double angle[NMax << 1], LI[NMax], LO[NMax];

int cmp(double a, double b)
{
    if (fabs(a-b) < EPS) return 0;
    if (a > b) return +1;
    return -1;
}

int cmp_angle(const PII& a, const PII& b)
{
    return atan2(a.y, a.x) < atan2(b.y, b.x);
}

int get_bit(int lin, int col)
{
    int b = col % BIT;
    
    return (A[lin][col/BIT] & (1<<b)) != 0;

}

void set_bit(int lin, int col)
{
    A[lin][col/BIT] += (1<<(col % BIT));
}

void gauss(void)
{
    int i, j, k, v, nrv, p = 0;

    nrv = (2*N+1) / BIT + 2;

    for (j = 1; j <= 2 * N; j++)
    {
        for (i = 1; i <= N; i++)
            if (!pivot[i] && get_bit(i, j))
            {
                pivot[i] = j;
                for (k = 1; k <= N; k++)
                    if (!pivot[k] && get_bit(k, j))
                        for (v = j/BIT; v <= nrv; v++)
                            A[k][v] ^= A[i][v];
                break;
            }
    }

    for (i = 1; i <= N; i++)
        R[i] = get_bit(i, 2*N+1);
       
    for (j = 2 * N; j >= 1; j--)
    {
        for (i = 1; i <= N; i++)
            if (pivot[i] == j)
            {
                Res[j] = R[i];
                for (k = 1; k <= N; k++)
                    if (get_bit(k, j))
                        R[k] ^= Res[j];
                break;
            }        
    }
}

int main(void)
{
    int i, j, xx;
    double ang;
    
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d %d %d %d", &seg[i].x.x, &seg[i].x.y, &seg[i].y.x, &seg[i].y.y);
        P[++h] = seg[i].x;
        P[++h] = seg[i].y;
    }

    sort(P+1, P+h+1, cmp_angle);
    P[h+1] = P[1];
    for (i = 1; i <= h+1; i++)
        angle[i] = atan2(P[i].y, P[i].x);

    for (i = 1; i <= N; i++)
    {
        LI[i] = atan2(seg[i].x.y, seg[i].x.x);
        LO[i] = atan2(seg[i].y.y, seg[i].y.x);
        if (cmp(LI[i], LO[i]) == 1)
            ang = LI[i], LI[i] = LO[i], LO[i] = ang;
    }
    
    for (i = 1; i <= h; i++)
    {
         ang = 0.5 * (angle[i] + angle[i+1]);
         for (j = 1; j <= N; j++)
            if (cmp(ang, LI[j]) >= 0 && cmp(ang, LO[j]) <= 0)
            {
               set_bit(j, i);
               W[j][i] = 1;
            }
    }

    for (i = 1; i <= N; i++)
    {
        scanf("%d", &xx);
        if (xx)
            set_bit(i, 2*N+1);

        W[i][2*N+1] = xx;
    }
    
    gauss();
    for (i = 1; i <= 2 * N; i++)
        cnt += Res[i];

    printf("%d\n", cnt);
    for (i = 1; i <= 2 * N; i++)
        if (Res[i])
        {
            ang = 0.5 * (angle[i] + angle[i+1]);
            if (cmp(ang, 0.0) < 0) ang += 2 * pi;
            printf("%.6lf\n", 180 * ang / pi);
        }


/*    for (i = 1; i <= N; i++)
    {
        for (j = 1; j <= 2 * N; j++)
            printf("%d ", W[i][j]);
        printf("| %d\n", W[i][2*N+1]);
    }*/

    
    return 0;
}