Cod sursa(job #1962346)

Utilizator tqmiSzasz Tamas tqmi Data 11 aprilie 2017 18:26:24
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <cmath>
#include <fstream>
#include <bitset>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("laser.in");
ofstream fout("laser.out");
const int Nmax=520;
int N,k,nr;
bitset <2*Nmax> a[Nmax],C;
struct capete
{
    double x,y;
    int n;
    double u;
};
capete p[2*Nmax];
double unghi[2*Nmax];
int poz[Nmax];
double get_a(capete b)
{
    double z=atan2(b.y,b.x);
    if(z<0)
        z=2*M_PI+z;
    return z;
}
void read()
{
    fin>>N;
    for(int i=1;i<=N;i++)
    {
        int x1,x2,y1,y2;
        fin>>x1>>y1>>x2>>y2;
        p[i].x=x1;
        p[i].y=y1;
        p[i].n=i;
        p[i].u=get_a(p[i]);
        p[i+N].x=x2;
        p[i+N].y=y2;
        p[i+N].n=i;
        p[i+N].u=get_a(p[i+N]);
        if(max(p[i].u,p[i+N].u)-min(p[i].u,p[i+N].u)>M_PI)
            C[i]=1;
    }
}

bool comp(capete a, capete b)
{
    return a.u<b.u;
}

bool check()
{
    for(int j=1;j<=N;j++)
        if(C[j])
            return 1;
    return 0;
}

void Bal()
{
    for(int i=1;i<=2*N;i++)
    {
        C[p[i].n]=C[p[i].n]^1;
        if(check())
        {
            k++;
            for(int j=1;j<=N;j++)
                a[j][k]=C[j];
            capete b;
            b.x=(p[i].x+p[i+1].x)/2;
            b.y=(p[i].y+p[i+1].y)/2;
            unghi[k]=get_a(b);
        }
    }
}

void Gauss()
{
    for(int i=1;i<=N;i++)
    {
        for(int j=0;j<=k && poz[i]==0;j++)
            if(a[i][j])
                poz[i]=j;
        if(!poz[i])continue;
        for(int j=1;j<=N;j++)
            if(j!=i && a[j][poz[i]])
                a[j]^=a[i];
    }
}


void solve()
{
    sort(p+1,p+2*N+1,comp);
    p[2*N+1]=p[1];
    Bal();
    for(int i=1;i<=N;i++)
    {
        int x;
        fin>>x;
        a[i][k+1]=x;
    }
    Gauss();
    for(int i=1;i<=N;i++)
        if(a[i][k+1])
         nr++;
    fout<<nr<<"\n";
    fout<<setprecision(10)<<fixed;
    for(int i=1;i<=N;i++)
        if(a[i][k+1])
            fout<<unghi[poz[i]]/M_PI*180<<"\n";
}

int main()
{
    read();
    solve();
    return 0;
}