Cod sursa(job #1604031)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 17 februarie 2016 21:52:21
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream f("laser.in");
ofstream g("laser.out");
int N;
vector <double> Angle;
const double PI = 3.14159265;
bool Value[515];
int A[515][4*515];
int X[4*515];
pair<double,double> Segment[515];
inline double makePositive(double x)
{
    if(x>=0)
        return x;
    return x+2*PI;
}

void Read()
{
    f>>N;
    for(int i=1;i<=N;i++)
    {
        int x1,y1,x2,y2;
        f>>x1>>y1>>x2>>y2;
        Angle.push_back(makePositive(atan2(x1,y1)));
        Angle.push_back(makePositive(atan2(x1,y2)));
        Segment[i]=make_pair(makePositive(atan2(x1,y1)),makePositive(atan2(x2,y2)));
    }
    sort(Angle.begin(),Angle.end());
    for(int i=1;i<=N;i++)
        f>>Value[i];
}

void insertNewElements()
{
    int len=Angle.size()-1;
    for(int i=0;i<len;i++)
        Angle.push_back((Angle[i]+Angle[i+1])/2);
    sort(Angle.begin(),Angle.end());
}

inline bool Intersect(double angle1,double angle2,double angle0)
{
    return angle0>=min(angle1,angle2) && angle0<=max(angle1,angle2);
}

void buildA()
{
    for(int i=1;i<=N;i++)
    {
        A[i][4*N+1]=Value[i];
        for(int j=0;j<Angle.size();j++)
            A[i][j+1]=Intersect(Segment[i].first,Segment[i].second,Angle[j]);
    }
}

void Gauss()
{
    int i=1,j=1;
    int M=4*N;
    while(i<=N&&j<=M)
        {
            int k;
            for(k=i;A[k][j]==0&&k<=N;k++);
            if(k==N+1)
            {
                j++;
                continue;
            }
            if(k!=i)
                swap(A[i],A[k]);

            for(int l=j+1;l<=M+1;l++)
                A[i][l]^=A[i][j];
            A[i][j]=1;
            for(k=i+1;k<=N;k++)
                {
                    for(int l=j+1;l<=M+1;l++)
                        A[k][l]^=(A[i][l]^A[k][j]);
                    A[k][j]=0;
                }
        ++i;++j;
        }
    int S=0;
    for(i=N;i>=1;i--)
        {
            S=0;
            for(j=1;j<=M+1;j++)
                if(A[i][j]!=0)
                    break;
            for(int k=j+1;k<=M;k++)
                S^=(A[i][k]^X[k]);
            X[i]=(A[i][M+1]^S)^A[i][i];
        }
    int ans=0;
    for(int i=1;i<=M;i++)
        if(X[i]==1)
            ++ans;
    g<<ans<<"\n";
    for(int i=1;i<=M;i++)
        if(X[i]==1)
            g<<fixed<<setprecision(15)<<(Angle[i-1]*180)/PI<<"\n";
}
int main()
{
    Read();
    insertNewElements();
    buildA();
    Gauss();
    return 0;
}