Cod sursa(job #37376)

Utilizator azotlichidAdrian Vladu azotlichid Data 24 martie 2007 22:49:45
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define CLEAR(X) (memset(X, 0, sizeof(X)))
#define FORI(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define FOR(i, N, M) for (int i = (int)(N); i <= (int)(M); ++i)
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SIZE(X) (int)((X).size())
#define TIPA(a, i) (cerr << #a << "[" #i " = " << (i) << "] = " << (a)[i] << endl)
#define TIP(x) (cerr << #x << " = " << (x) << endl)

#define MP make_pair
#define PB push_back
#define INF 0x3F3F3F3F

typedef long long LL;

#define NMAX 512
const double pi = 3.1415926535897932384626433832795;

int N, M, x, y, z, t, flag, a[NMAX][NMAX], b[NMAX], r[NMAX], f[NMAX];
pair<double, double> s[NMAX];
vector<double> u, d;

double grad(double x) { return x * 180.0 / pi; }

double op(double u) // (-pi, pi]
{
    u += pi;
    while (u > pi) u -= 2*pi;
    return u;
}

int inter(int p, double u)
{
    int r = 0;
    if (s[p].first + pi < s[p].second) r = 1;
    return s[p].first < u && u < s[p].second ? (1 ^ r) : r;
}

void baga(int p, double u)
{
    REP(i, N)
        if (inter(i, u))
            a[i][p] = 1;
}

void swapln(int x, int y)
{
    if (x == y) return;
    REP(i, 2*N) swap(a[x][i], a[y][i]);
    swap(b[x], b[y]);
}

void swapcl(int x, int y)
{
    if (x == y) return;
    REP(i, N) swap(a[i][x], a[i][y]);
    swap(f[x], f[y]);
}

int emptycl(int x)
{
    REP(i, N) if (a[i][x]) return 0;
    return 1;
}

int main(void)
{
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);
    scanf("%d", &N);
    REP(i, N)
    {
        scanf("%d %d %d %d", &x, &y, &z, &t);
        s[i] = MP(atan2((double)y, x), atan2((double)t, z));
        u.PB(s[i].first), u.PB(s[i].second);
        if (s[i].first > s[i].second) swap(s[i].first, s[i].second);
    }
    REP(i, N) scanf("%d", &b[i]);
    sort(ALL(u));
    u.PB(u[0]);

    CLEAR(a);
    REP(i, 2*N-1) baga(i, (u[i]+u[i+1])/2), d.PB(grad((u[i]+u[i+1])/2));
    baga(2*N-1, op((u[2*N-1]+u[0])/2)), d.PB(grad(op((u[2*N-1]+u[0])/2)));

    M = 2*N;
    REP(i, 2*N) f[i] = i;
    REP(i, N)
    {
        while (emptycl(i) && i < M) swapcl(i, M-1), -- M;
        if (i == M) { N = i; break; }
        FOR(l, i, N-1) if (a[l][i]) { swapln(i, l); break; }
        FOR(l, i+1, N-1) if (a[l][i])
        {
            REP(j, M) a[l][j] ^= a[i][j];
            b[l] ^= b[i];
        }
    }

    for (int i = N-1; i >= 0; i --)
    {
        r[i] = b[i];
        FOR(j, i+1, N-1) r[i] ^= (a[i][j] * r[j]);
    }

    int Ans = 0;
    REP(i, N) Ans += r[i];
    printf("%d\n", Ans);
    REP(i, N) if (r[i])
        printf("%0.6lf\n", d[i]);
    
    return 0;
}