Cod sursa(job #961114)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 17:14:02
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 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 = 1; k <= N; k++)
            if(i != k && B[k][j]) B[k] ^= B[i];
        i++; j++;
    }
    for(int i = 1, j; i <= N; i++)
    {
        for(j = 1; j <= M; j++)
            if(B[i][j] && B[i][M + 1] && !X[j])
            {
                sol++;
                X[j] = true;
                break;
            }
    }
    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;
}