Cod sursa(job #728362)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 28 martie 2012 17:55:51
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <stdio.h>
#include <bitset>
#include <algorithm>
#include <math.h>
#define NMAX 521
#define LMAX 1055
#define pdd pair <double,double>
#define f first
#define s second
using namespace std;
int n,m,stare[NMAX],rez;
pdd A[NMAX];
double B[LMAX],C[LMAX];
bitset <LMAX> D[NMAX],aux;
bool sol[LMAX];

double angle(double x,double y)
{
	double alfa=atan2(y,x)*180/M_PI;
	return alfa<0 ? alfa+360 : alfa;
}
void read()
{
	scanf("%d",&n);
	int i;
	double x,y,aux;
	for (i=1; i<=n; i++)
	{
		scanf("%lf%lf",&x,&y);
		A[i].f=angle(x,y);
		scanf("%lf%lf",&x,&y);
		A[i].s=angle(x,y);
		if (A[i].f>A[i].s)
			aux=A[i].f,A[i].f=A[i].s,A[i].s=aux;
		B[++m]=A[i].f; B[++m]=A[i].s;
	}
	for (i=1; i<=n; i++)
		scanf("%d",&stare[i]);
}
inline double modul(double x)
{
	return x<0 ? -x : x;
}
void prepare()
{
	sort(B+1,B+m+1);
	B[m+1]=B[1];
	int i,j;
	double alfa;
	for (i=1; i<=m; i++)
	{
		alfa=modul(B[i+1]-B[i]);
		alfa=alfa>180 ? 360-alfa : alfa;
		alfa/=2;
		C[i]=B[i]+alfa;
		C[i]=C[i]>360 ? C[i]-360 : C[i];
	}
	for (i=1; i<=m; i++)
		for (j=1; j<=n; j++)
			if (A[j].f<C[i] && C[i]<A[j].s)
				D[j][i]=1;
	for (i=1; i<=n; i++)
		D[i][m+1]=stare[i];
}
void swap(int lx,int ly)
{
	aux=D[lx]; D[lx]=D[ly]; D[ly]=aux;
}
void gauss()
{
	int i=1,j=1,k;
	while (i<=n && j<=m)
	{
		for (k=i; k<=n; k++)
			if (D[k][j])
				break ;
		if (k==n+1)
		{
			j++;
			continue ;
		}
		if (i!=k)
			swap(i,k);
		for (k=i+1; k<=n; k++)
			if (D[k][j])
				D[k]^=D[j];
		i++; j++;
	}
	for (i=n; i>=1; i--)
		for (j=1; j<=m+1; j++)
			if (D[i][j])
			{
				sol[j]=D[i][j+1];
				for (k=m; k>j; k--)
					sol[j]^=sol[k];
			}
	for (i=1; i<=m; i++)
		if (sol[i])
			rez++;
	printf("%d\n",rez);
	for (i=1; i<=m; i++)
		if (sol[i])
			printf("%lf\n",C[i]);
}
int main()
{
	freopen("laser.in","r",stdin);
	freopen("laser.out","w",stdout);
	read();
	prepare();
	gauss();
	return 0;
}