Pagini recente » Cod sursa (job #424857) | Cod sursa (job #734914) | Cod sursa (job #1741954) | Statistici Badoiu Alexia Ana-Maria (alexiabad) | Cod sursa (job #1604831)
#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 mod(double x)
{
return max(x,-x);
}
inline double makePositive(int x1,int y1)
{
double x=atan2(mod(x1),mod(y1));
x*=180/PI;
if(x1>=0 && y1>=0);
if(x1>=0 && y1<0)
{
x-=90;
if(x<0)
x=360+x;
}
if(x1<0 && y1>=0)
{
x+=90;
}
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());
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)
{
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][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]);
A[i][j]=0;
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;
}