Cod sursa(job #842209)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 26 decembrie 2012 14:29:01
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <fstream>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <iomanip>

#define f first
#define s second
#define mp make_pair
#define MAX 550
#define PI 3.14159265
#define EPS 1e-5
#define PDD pair<double, double>

using namespace std;

int N, M, a, X1, X2, Y1, Y2, sol;
PDD V[MAX];
double A[MAX << 1];
bitset< MAX << 1 > B[MAX], X;

double getAngle(int x, int y)
{
    double rez = atan2(1.0 * y, 1.0 * x) * 180.0 / PI;
    if(rez < 0.0) rez += 360.0;
    return rez;
}

void citire()
{
    ifstream in("laser.in"); in>>N;
    for(int i = 1; i <= N; i++)
    {
        in>>X1>>Y1>>X2>>Y2;
        V[i].f = getAngle(X1, Y1);
        V[i].s = getAngle(X2, Y2);
        if(V[i].f > V[i].s) swap(V[i].f, V[i].s);
        A[i] = V[i].f; A[i + N] = V[i].s;
    } M = 2 * N; sort(A + 1, A + M + 1);
    for(int i = 1; i <= N; i++)
    {
        in>>a;
        B[i][M + 1] = a;
    } in.close();
}

int main()
{
    citire(); A[M + 1] = A[1] + 360.0;
    for(int i = 1; i <= M; i++)
    {
        A[i] = (A[i] + A[i + 1]) / 2.0;
        if(A[i] > 360.0) A[i] -= 360.0;
    }
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(V[i].s - V[i].f < 180.0 + EPS)
                B[i][j] = (V[i].f - EPS < A[j] && A[j] < V[i].s + EPS);
            else
                B[i][j] = (V[i].f + EPS > A[j] || A[j] > V[i].s - EPS);
    int i = 1, j = 1, k;
    while(i <= N && j <= M)
    {
        for(k = i; k <= N && !B[k][j]; k++);
        if(k > N) { j++; continue; }
        swap(B[i], B[k]);
        for(k = i + 1; k <= N; k++)
            if(B[k][j]) B[k] ^= B[i];
        i++; j++;
    }
    for(int i = N, j; i; i--)
    {
        for(j = 1; j <= M; j++)
            if(B[i][j])
            {
                X[j] = B[i][M + 1];
                for(int k = j + 1; k <= M; k++) X[j] = X[j] ^ (B[i][k] & X[k]);
                break;
            }
    }
    for(int i = 1; i <= M; i++) if(X[i]) sol++;
    ofstream out("laser.out");
    out<<sol<<"\n";
    for(int i = 1; i <= M; i++) if(X[i]) out<<fixed<<setprecision(6)<<A[i]<<"\n";
    out.close();
    return 0;
}