Cod sursa(job #36999)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 24 martie 2007 14:22:25
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define PII pair<int,int>
#define f first
#define s second
#define mp make_pair 
#define nmax 512
#define mmax 1024
#define left (i<<1)
#define right ((i<<1)|1)
#define PI 3.141592653
#define EPS 1e-7

int n,m,A[nmax][mmax],H[mmax],sol[mmax],rez;
pair <PII,PII> P[nmax];
double X[mmax],Y[mmax];

double mytan(PII A)
{
	double x=atan2(A.s,A.f);
	if(x+EPS<0)
		x+=2*PI;
	return x;
}

int test(double a,double b,double c)
{
	return a-EPS<b&&b<c+EPS;
}

int main()
{
	freopen("laser.in","r",stdin);
	freopen("laser.out","w",stdout);
	int i,j,p,k;
	double a,b,c;
	scanf("%d",&n);
	FOR(i,0,n)
	{
		scanf("%d %d %d %d",&P[i].f.f,&P[i].f.s,&P[i].s.f,&P[i].s.s);
		X[left]=mytan(P[i].f);
		X[right]=mytan(P[i].s);
	}
	m=2*n;
	sort(X,X+m);

	FOR(i,0,m-1)
		Y[i]=(X[i]+X[i+1])/2.0;
	Y[m-1]=(X[0]+2*PI+X[m-1])/2.0;
	if(Y[m-1]+EPS>2*PI)
		Y[m-1]-=2*PI;

	FOR(i,0,n)
	{
		scanf("%d",&A[i][m]);
		a=mytan(P[i].f);
		b=mytan(P[i].s);
		if(a>b)
			c=a,a=b,b=c;
		if(b-a>PI)
			c=a,a=b,b=c+2*PI;
		FOR(j,0,m)
		{
			if(test(a,Y[j],b)||test(a,Y[j]+2*PI,b))
				A[i][j]=1;
			else
				A[i][j]=0;
		}
	}

	p=0;
	FOR(k,0,m)
	{
		FOR(i,p,n)
			if(A[i][k])
				break;
		if(i==n)
		{
			H[k]=-1;
			continue;
		}
		FOR(j,0,m+1)
			swap(A[p][j],A[i][j]);
		FOR(i,p+1,n)
		{
			if(!A[i][k])
				continue;
			FOR(j,0,m+1)
				A[i][j]^=A[p][j];
		}
		H[k]=p++;
	}

	for(k=m-1;k>=0;k--)
	{
		if(H[k]==-1)
		{
			sol[k]=0;
			continue;
		}
		sol[k]=A[H[k]][m];
		FOR(i,k+1,m)
			if(H[k]!=-1)
				sol[k]^=(A[H[k]][i]&sol[i]);		
		if(sol[k])
			rez++;
	}
	
	printf("%d\n",rez);
	FOR(i,0,m)
		if(sol[i])
			printf("%lf\n",Y[i]/PI*180);

	return 0;
}