Pagini recente » Istoria paginii runda/rar19/clasament | Istoria paginii runda/rar20/clasament | Monitorul de evaluare | Istoria paginii runda/rar19/clasament | Cod sursa (job #1252034)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define x first
#define y second
using namespace std;
const double eps=0.00000001;
double angle[1030];
pair<double,double> seg[520];
char v[520][1030],sol[1030];
double getangle(int x, int y)
{
double a=atan2(y,x)*180.0/acos(-1);
if(a<0.0) a+=360.0;
return a;
}
int main()
{
freopen("laser.in", "r", stdin);
freopen("laser.out", "w", stdout);
int n;
scanf("%d",&n);
int m=2*n;
for(int i=1;i<=n;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
seg[i].x=getangle(x1,y1);
seg[i].y=getangle(x2,y2);
if(seg[i].x>seg[i].y) swap(seg[i].x,seg[i].y);
angle[i]=seg[i].x;
angle[i+n]=seg[i].y;
}
for(int i=1;i<=n;i++) scanf("%d",&v[i][m+1]);
sort(angle+1,angle+m+1);
angle[m+1]=angle[1]+360.0;
for(int i=1;i<=m;i++)
{
angle[i]=(angle[i]+angle[i+1])/2.0;
if(angle[i]>360.0) angle[i]-=360.0;
}
for(int i=1;i<=n;i++)
if(seg[i].y-seg[i].x<180.0+eps)
for(int j=1;j<=m;j++) v[i][j]=(angle[j]>=seg[i].x-eps && angle[j]<=seg[i].y+eps);
else for(int j=1;j<=m;j++) v[i][j]=(angle[j]<=seg[i].x+eps || angle[j]>=seg[i].y-eps);
int i=1,j=1,q;
while(i<=n && j<=m)
{
for(q=i;q<=n;q++) if(v[q][j]) break;
if(q==n+1) {j++;continue;}
if(q>i) swap(v[i],v[q]);
for(q=i+1;q<=n;q++)
if(v[q][j]) for(int k=j;k<=m+1;k++) v[q][k]^=v[i][k];
i++;j++;
}
for(i=n;i;i--)
for(j=i;j<=m;j++)
if(v[i][j])
{
sol[j]=v[i][m+1];
for(q=j+1;q<=m;q++) sol[j]^=v[i][q]&sol[q];
break;
}
int nr=0;
for(int i=1;i<=m;i++) if(sol[i]) nr++;
printf("%d\n",nr);
for(i=1;i<=m;i++) if(sol[i]) printf("%lf\n",angle[i]);
return 0;
}