Cod sursa(job #42625)

Utilizator victorsbVictor Rusu victorsb Data 29 martie 2007 12:59:08
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define Nmax 1030
#define pct pair<int, int>
#define x first
#define y second

const double eps = 1.0e-12;
int n;
pct punct[Nmax];
double pan[Nmax], p[Nmax];
int mat[Nmax][Nmax], b[Nmax], v[Nmax];

double nrml(double a)
{
    while (a < 0)
        a += 360;
    while (a > 360)
        a -= 360;
    return a;
}

void citire()
{
    int i;
    
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
        scanf("%d %d %d %d", &punct[i].x, &punct[i].y, &punct[i + n].x, &punct[i + n].y);
    
    for (i = 1; i <= n; ++i)
        scanf("%d", &b[i]);
    
    for (i = 1; i <= 2*n; ++i)
        p[i] = nrml(atan2(punct[i].y, punct[i].x) * 180 / M_PI);
    sort(p + 1, p + 2*n + 1);
    
    for (i = 1; i <= 2*n - 1; ++i)
        pan[i] = nrml((p[i] + p[i + 1]) / 2);
    pan[2*n] = nrml((360 + p[1] + p[2*n]) / 2);
    sort(pan+1, pan+2*n+1);
}

int intersect(double x1, double y1, double x2, double y2, double x3, double y3)
{
    double p1 = x2 * y1 - x1 * y2;
    double p2 = x3 * y1 - x1 * y3;
    
    if (p1 * p2 > - eps)
        return 0;
    
    
    x3 -= x2;
    y3 -= y2;
    
    x1 -= x2;
    y1 -= y2;
    
    x2 = -x2;
    y2 = -y2;
    
    p1 = x2 * y3 - x3 * y2;
    p2 = x1 * y3 - x3 * y1;
    
    if (p1 * p2 < - eps)
        return 1;
    
    return 0;
}

void gauss()
{
    int i, j, k, piv;
    piv = 1;
    for (i = 1; i <= 2 * n && piv <= n; ++i)
    {
        for (j = piv; j <= n; ++j)
            if (mat[j][i] == 1)
                break;
        
        if (piv != j && mat[j][i] == 1)
        {
            for (k = 1; k <= 2 * n; ++k)
                swap(mat[piv][k], mat[j][k]);
            swap(b[piv], b[j]);
        }
        
        if (mat[piv][i] == 0)
            continue;
        
        for (j = 1; j <= n; ++j)
            if (piv != j && mat[j][i] == 1)
            {
                for (k = 1; k <= 2 * n; ++k)
                    mat[j][k] ^= mat[piv][k];
                b[j] ^= b[piv];
            }
        
        ++piv;
    }
}

void solve()
{
    int i, j, ct = 0;
    double x1, y1;
    
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= 2 * n; ++j)
        {
            x1 = cos(pan[j] * M_PI / 180) * 50000;
            y1 = sin(pan[j] * M_PI / 180) * 50000;
            
            if (intersect(x1, y1, punct[i].x, punct[i].y, punct[i+n].x, punct[i+n].y))
                mat[i][j] = 1;
            else
                mat[i][j] = 0;
        }
    }
    
    gauss();

    for (i = 1; i <= n; ++i)
        for (j = 1; j <= 2 * n; ++j)
            if (mat[i][j] == 1)
            {
                v[j] = b[i];
                break;
            }
    
    
    for (i = 1; i <= 2 * n; ++i)
        if (v[i]) ++ct;
    
    printf("%d\n", ct);
    
    for (i = 1; i <= 2 * n; ++i)
        if (v[i])
            printf("%.6lf\n", pan[i]);
}

int main()
{
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);
    citire();
    solve();
    return 0;
}