Cod sursa(job #324592)

Utilizator AndreyPAndrei Poenaru AndreyP Data 16 iunie 2009 15:53:19
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 kb
#include<stdio.h>
#include<math.h>
#include<bitset>
#include<algorithm>
using namespace std;
#define N 520
#define fs first
#define sc second
#define mp make_pair
const double eps=1e-6;
const double pi=3.14159265;
int n,m;
double unghi[N<<1];
double bis[N<<1];
double sol[N<<1];
pair<double,double> seg[N];
bitset<(N<<1)> eq[N],sec;
inline char cmp(double x,double y)
{
	if(x+eps<y)
		return -1;
	if(y+eps<x)
		return 1;
	return 0;
}
inline double convert(double x,double y)
{
	return acos(x/(sqrt(x*x+y*y)))*180.00000/pi;
}
bool compar(const double &x,const double &y)
{
	if(cmp(x,y)==-1)
		return true;
	return false;
}
inline void citire()
{
	scanf("%d",&n);
	int aux=-1;
	int x1,y1,x2,y2;
	double un;
	for(int i=0; i<n; ++i)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		un=convert((double)x1,(double)y1);
		if(y1<0)
			un+=180.00000;
		if(cmp(un,360.00000)!=-1)
			un-=360.00000;
		seg[i].fs=un;
		unghi[++aux]=un;
		un=convert((double)x2,(double)y2);
		if(y2<0)
			un+=180.00000;
		if(cmp(un,360.00000)!=-1)
			un-=360.00000;
		seg[i].sc=un;
		unghi[++aux]=un;
		if(cmp(seg[i].fs,seg[i].sc)==1)
			swap(seg[i].fs,seg[i].sc);
	}
	sort(unghi,unghi+aux+1,compar);
}
inline bool vezi(pair<double,double> s,double un)
{
	double aux=s.sc-s.fs;
	if(cmp(aux,180.00000)!=1)
	{
		if(cmp(s.fs,un)!=1 && cmp(un,s.sc)!=1)
			return true;
		return false;
	}
	else
	{
		if(cmp(s.fs,un)!=-1 && cmp(un,s.sc)!=-1)
			return true;
		return false;
	}
}
inline void make_eq()
{
	m=n<<1;
	unghi[m]=unghi[0];
	if(cmp(unghi[m],unghi[m-1])==-1)
		unghi[m]+=360.00000;
	for(int i=0; i<m; ++i)
		bis[i]=(unghi[i+1]-unghi[i])/2+unghi[i];
	if(cmp(bis[m-1],360.00000)!=-1)
		bis[m-1]-=360.00000;
	int aux;
	for(int i=0; i<n; ++i)
	{
		for(int j=0; j<m; ++j)
		{
			if(vezi(seg[i],bis[j]))
				eq[i][j]=1;
		}
		scanf("%d",&aux);
		eq[i][m]= (aux==0) ? 0 : 1;
	}
}
inline void rezolva()
{
	int r1;
	bitset<(N<<1)> baux;
	for(int col=0,rand=0; col<m; ++col)
	{
		for(r1=rand; r1<n && !eq[r1][col]; ++r1)
			;
		if(r1==n)
		{
			sec[col]=1;
			continue;
		}
		if(r1!=rand)
		{
			baux=eq[rand];
			eq[rand]=eq[r1];
			eq[r1]=baux;
		}
		for(int i=rand+1; i<n; ++i)
		{
			if(eq[i][col])
				eq[i]^=eq[rand];
		}
		++rand;
	}
	int nrez=0;
	for(int i=0; i<m; ++i)
	{
		if(sec[i])
		{
			for(int j=0; j<n; ++j)
			{
				if(eq[j][i])
					eq[j][i]=0;
			}
		}
	}
	bitset<1> val;
	for(int col=m-1,rand=n-1; col>=0; --col)
	{
		if(sec[col])
			continue;
		for(; !eq[rand][col] && rand>0; --rand)
			;
		val[0]=eq[rand][m];
		if(val==1)
			sol[++nrez]=bis[col];
		for(int i=0; i<n; ++i)
		{
			if(eq[i][col])
			{
				eq[i][col]=0;
				eq[i][m]= (val[0]==1) ? !eq[i][m] : eq[i][m];
			}
		}
	}
	printf("%d\n",nrez);
	for(int i=1; i<=nrez; ++i)
		printf("%lf\n",sol[i]);
}
int main()
{
	freopen("laser.in","r",stdin);
	freopen("laser.out","w",stdout);
	citire();
	make_eq();
	rezolva();
	/*for(int i=0; i<n; ++i)
		printf("%lf %lf\n",seg[i].fs,seg[i].sc);
	for(int i=0; i<m; ++i)
		printf("%lf ",bis[i]);
	printf("\n");
	for(int i=0; i<m; ++i)
		printf("%lf ",unghi[i]);
	printf("\n");*/
	return 0;
}