Cod sursa(job #1606156)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 19 februarie 2016 22:58:34
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 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,Angle2;
const double PI = acos(-1);
bool Value[515];
int A[515][4*515];
int X[4*515];
pair<double,double> Segment[515];
inline double mod(double x)
{
    return max(x,-x);
}
inline double makePositive(int x1,int y1)
{
    double x=atan2(mod(y1),mod(x1));
    x*=180;
    x/=PI;
    if(x1>=0 && y1>=0);
    if(x1>=0 && y1<0)
    {
        x=360-x;
    }
    if(x1<0 && y1>=0)
    {
        x=180-x;
    }
    if(x1<0 && y1<0)
        x+=180;
    return x;
}

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(x1,y1));
        Angle.push_back(makePositive(x2,y2));
        Segment[i]=make_pair(makePositive(x1,y1),makePositive(x2,y2));
    }
    sort(Angle.begin(),Angle.end());
    Angle.push_back(Angle[0]);
    for(int i=1;i<=N;i++)
        f>>Value[i];
}
double Bisect(double x,double y)
{
    if(x<=y)
        return (x+y)/2;
    y+=360;
    double s=x+y;
    s/=2;
    if(s>=360)
        s-=360;
    return s;
}
void insertNewElements()
{
    int len=Angle.size()-1;
    for(int i=0;i<len;i++)
        Angle2.push_back(Bisect(Angle[i],Angle[i+1]));
    sort(Angle2.begin(),Angle2.end());
    Angle.clear();
    Angle=Angle2;
}

inline bool Intersect(double angle1,double angle2,double angle0)
{
    if(angle1>angle2)
        swap(angle1,angle2);
    if(angle2-angle1<=180)
        return angle0>=angle1 && angle0<=angle2;
    return angle0<=angle1 || angle0>=angle2;
}

void buildA()
{
    for(int i=1;i<=N;i++)
    {
        A[i][Angle.size()+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=Angle.size();
    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(k=i+1;k<=N;k++)
                {
                    if(A[k][j]==0)
                        continue;
                    for(int l=j+1;l<=M+1;l++)
                        A[k][l]=A[i][l]^A[k][l];
                    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++)
            {
                if(A[i][k]==1)
                    S^=X[k];
            }

            X[j]=(A[i][M+1]^S);
        }
    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]<<"\n";
}
int main()
{
    Read();
    insertNewElements();
    buildA();
    Gauss();
    return 0;
}