Cod sursa(job #728533)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 28 martie 2012 19:35:19
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 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,aux2;
	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)
			aux2=A[i].f,A[i].f=A[i].s,A[i].s=aux2;
		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);
	int i,j;
	double alfa;
	for (i=1; i<m; i++)
		C[i]=(B[i]+B[i+1])/2;
	C[m]=(B[m]+360+B[1])/2;
	C[m]=C[m]>360 ? C[m]-360 : C[m];
	
	for (i=1; i<=m; i++)
		for (j=1; j<=n; j++)
		{
			alfa=A[j].s-A[j].f;
			if (alfa<180)
			{
				if (A[j].f<C[i] && C[i]<A[j].s)
					D[j][i]=1;
			}
			else
			{
				if (C[i]>A[j].s || C[i]<A[j].f)
					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[i];
		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--)
					if (D[i][k])
						sol[j]^=sol[k];
				break ;
			}
	for (i=1; i<=m; i++)
		if (sol[i])
			rez++;
	printf("%d\n",rez);
	for (i=1; i<=m; i++)
		if (sol[i])
			printf("%.6lf\n",C[i]);
}
int main()
{
	freopen("laser.in","r",stdin);
	freopen("laser.out","w",stdout);
	read();
	prepare();
	gauss();
	return 0;
}