Cod sursa(job #1096117)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 1 februarie 2014 15:51:51
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define NM 530
#define x first
#define y second
#define EPS 1e-7
#define TT 3.1415926535897932384626433832795

using namespace std;

ifstream f("laser.in");
ofstream g("laser.out");

inline bool Equal (double x, double y)
{
    return fabs(x-y)<EPS;
}

typedef pair<double, double> PI;
int N, M, CNT;
PI V[2*NM];
vector<double> Angle, Aux;
bool Hit[NM][2*NM], Sol[2*NM];

double GetAng (PI P)
{
    double ret=atan2(P.y, P.x)/TT * 180.0;
    if (ret<0)
        ret+=360.0;
    return ret;
}

int main ()
{
    f >> N;
    for (int i=1; i<=N; i++)
    {
        f >> V[i].x >> V[i].y;
        f >> V[i+N].x >> V[i+N].y;
        Aux.push_back(GetAng(V[i]));
        Aux.push_back(GetAng(V[i+N]));
    }

    sort(Aux.begin(), Aux.end());
    for (int i=0; i<Aux.size()-1; i++)
    {
        double v=(Aux[i]+Aux[i+1])*0.5;
        if (v>360.0) v-=360.0;
        Angle.push_back((Aux[i]+Aux[i+1])*0.5);
    }

    M=Angle.size();
    for (int i=1; i<=N; i++)
    {
        double p1=GetAng(V[i]);
        double p2=GetAng(V[i+N]);
        if (p1>p2+EPS)
            swap(p1, p2);

        if (p2-p1<180.0+EPS)
        {
            for (int j=0; j<M; j++)
                if (p1-EPS<=Angle[j] && Angle[j]<=p2+EPS)
                    Hit[i][j+1]=1;
        }
        else
        {
            for (int j=0; j<M; j++)
                if (p2-EPS<=Angle[j] || Angle[j]<=p1+EPS)
                    Hit[i][j+1]=1;
        }
    }

    for (int i=1; i<=N; i++)
        f >> Hit[i][M+1];

    int i=1, j=1;

    while (i<=N && j<=M)
    {
        int poz=0;
        for (int k=1; k<=N && poz==0; k++)
            if (Hit[k][j]==1)
                poz=k;
        if (poz==0)
        {
            j++;
            continue;
        }

        for (int k=1; k<=M+1; k++)
            swap(Hit[i][k], Hit[poz][k]);

        for (int k=i+1; k<=N; k++)
            if (Hit[k][j]==1)
                for (int t=1; t<=M+1; t++)
                    Hit[k][t]^=Hit[i][t];

        i++;
        j++;
    }

    for (int i=N; i>=1; i--)
        for (int j=1; j<=M+1; j++)
            if (Hit[i][j])
            {
                Sol[j]=Hit[i][M+1];
                for (int k=M; k>j; k--)
                    Sol[j]^=Sol[k]&Hit[i][k];
                CNT+=Sol[j];
                break;
            }

    g << CNT << '\n';
    for (int i=1; i<=M; i++)
        if (Sol[i])
            g << fixed << setprecision(6) << Angle[i-1] << '\n';

    f.close();
    g.close();

    return 0;
}