Cod sursa(job #42576)

Utilizator victorsbVictor Rusu victorsb Data 29 martie 2007 12:35:30
Problema Laser Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 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 + eps < 0)
        a += 360;
    while (a - eps > 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 + eps);
    pan[2*n] = nrml((360 + p[1] + p[2*n] + eps) / 2);
    sort(pan+1, pan+2*n+1);
}

int intersect(double a, double b, double aa, double bb, double cc, double &x0, double &y0)
{
    if (fabs(bb) < eps)
    {
        y0 = a * x0;
        return 0;
    }
    if (fabs(a / b - aa / bb) < eps)
        return -1;
    
    x0 = cc / (aa * b - a * bb);
    y0 = (a * cc) / (aa * b - a * bb);
    
    return 0;
}

void gauss()
{
    int i, j, k, piv;
    piv = 1;
    for (i = 1; i <= 2 * n; ++i)
    {
        for (j = piv; j <= n; ++j)
            if (mat[j][i] == 1)
                break;
        
        if (i != 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;
    
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= 2 * n; ++j)
        {
            double x0, y0;
            double a = punct[i].y - punct[i + n].y;
            double b = punct[i + n].x - punct[i].x;
            double c = punct[i].x * punct[i + n].y - punct[i + n].x * punct[i].y;
            x0 = punct[i].x;
            y0 = punct[i].y;
            
            if (intersect(tan(pan[j] * M_PI / 180), -1.0, a, b, c, x0, y0) == -1)
                mat[i][j] = 0;
            else if ((min(punct[i].x, punct[i+n].x) - eps < x0 && x0 < max(punct[i].x, punct[i+n].x) + eps) &&
                     (min(punct[i].y, punct[i+n].y) - eps < y0 && y0 < max(punct[i].y, punct[i+n].y) + eps))
                if (fabs(nrml(atan2(y0, x0) * 180 / M_PI) - pan[j]) < eps)
                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;
}