Cod sursa(job #1783334)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 18 octombrie 2016 22:22:49
Problema Laser Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN 550

using namespace std;

struct coord
{
    double x, y;
    coord(double x = 0, double y = 0) : x(x), y(y) { }
};
struct segm
{
    coord st, dr;
};
segm a[MAXN];
int n;
int f[MAXN], nq, go[MAXN];
int c[MAXN][2*MAXN], sol[2*MAXN];
double EPS = 0.00001;
double d[2*MAXN];

void read()
{
    scanf("%d\n", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf %lf %lf %lf", &a[i].st.x, &a[i].st.y, &a[i].dr.x, &a[i].dr.y);
    for (int i = 1; i <= n; i++)
        scanf("%d ", &f[i]);
}
inline double angle(double x, double y) {
    double angle = atan2(y, x) * 180.0 / 3.1415926;
    if (angle < 0) angle += 360;
    return angle;
}

double build(coord st, coord dr)
{
    coord mij = coord((st.x+dr.x)/2, (st.y+dr.y)/2);
    return angle(mij.x, mij.y);
}

bool inter(double dt, segm s) /// returns whether dt intersects s
{
    double ast = angle(s.st.x, s.st.y);
    double adr = angle(s.dr.x, s.dr.y);
    if (ast > adr) swap(ast, adr);
    if (adr - ast < 180+EPS)
        return (ast-EPS < dt && dt < adr+EPS);
    return (dt < ast+EPS || dt > adr-EPS);
}

void prepare()
{
    a[n+1] = a[1];
    for (int i = 1; i <= n; i++) {
        d[++nq] = angle(a[i].st.x, a[i].st.y);
        d[++nq] = angle(a[i].dr.x, a[i].dr.y);
    }
    sort(d+1, d+nq+1);
    d[nq+1] = d[1];
    for (int i = 1; i <= nq; i++) {
        if (d[i+1] - d[i] > 180)
            d[i] = (d[i] + 360 + d[i+1]) / 2;
        d[i] = (d[i] + d[i+1]) / 2;
        if (d[i] < 0) d[i] += 360;
        if (d[i] > 360) d[i] -= 360;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= nq; j++)
            c[i][j] = inter(d[j], a[i]);
        c[i][nq+1] = f[i];
    }
    nq++;
}

void solve()
{
    for (int i = 1, j = 1; i <= n && j <= nq; j++) {
        int ok = 0;
        for (int x = i; x <= n && !ok; x++)
            if (c[x][j] != 0) {
                for (int p = 1; p <= nq; p++)
                    swap(c[i][p], c[x][p]);
                ok = 1;
            }
        if (!ok) continue;
        for (int ki = i+1; ki <= n; ki++) {
            int val = c[ki][j];
            for (int kj = j; kj <= nq; kj++)
                c[ki][kj] ^= val;
        }
        go[i] = j;
        i++;
    }
    for (int i = n; i >= 1; i--) {
        int sum = 0;
        for (int j = go[i]+1; j < nq; j++)
            sum ^= (c[i][j] && sol[j]);
        sol[go[i]] = sum ^ c[i][nq];
    }
}

void afisare()
{
    int cnt = 0;
    for (int i = 1; i < nq; i++)
        if (sol[i]) cnt++;
    printf("%d\n", cnt);
    for (int i = 1; i < nq; i++)
        if (sol[i])
            printf("%f\n", d[i]);
}

int main()
{
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);

    read();
    prepare();
    solve();
    afisare();

    return 0;
}