Cod sursa(job #2785268)

Utilizator stefantagaTaga Stefan stefantaga Data 18 octombrie 2021 13:18:21
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <algorithm>
#define NMAX 515
#define LMAX 1035
#define eps 1e-10
#define pdd pair <double,double>
#define x first
#define y second
using namespace std;
int n,m,stare[NMAX],sol[LMAX],rez;
pdd A[NMAX],pct;
double B[LMAX],C[LMAX];
bitset <LMAX> D[NMAX],aux_l;
double angle(pdd a)
{
	double val=atan2(a.y,a.x)*180/M_PI;
	return val<0 ? val+360 : val;
}
void read()
{
	scanf("%d",&n);
	int i;
	double aux;
	for (i=1; i<=n; i++)
	{
		scanf("%lf%lf",&pct.x,&pct.y);
		A[i].x=angle(pct);
		scanf("%lf%lf",&pct.x,&pct.y);
		A[i].y=angle(pct);
		if (A[i].x>A[i].y)
			aux=A[i].x,A[i].x=A[i].y,A[i].y=aux;
		B[++m]=A[i].x; B[++m]=A[i].y;
	}
	for (i=1; i<=n; i++)
		scanf("%d",&stare[i]);
}
void prep()
{
	sort(B+1,B+m+1);
	B[m+1]=B[1];
	int i,j;
	for (i=1; i<=m; i++)
	{
		C[i]=(B[i]+B[i+1])/2;
		if (C[i]>360) C[i]-=360;
	}

	for (i=1; i<=n; i++)
	{
		for (j=1; j<=m; j++)
		{
			if (A[i].y-A[i].x<(double)180+eps)
			{
				if (C[j]+eps>A[i].x && C[j]<A[i].y+eps)
					D[i][j]=1;
			}
			else
			{
				if ((C[j]+eps<A[i].x && C[j]>-eps) || (C[j]-180>-eps && C[j]+eps>A[i].y))
					D[i][j]=1;
			}
		}
		D[i][m+1]=stare[i];
	}
}
void swap_l(int l1,int l2)
{
	aux_l=D[l1]; D[l1]=D[l2]; D[l2]=aux_l;
}
void solve()
{
	prep();
	int i=1,j=1,k,poz;
	while (i<=n && j<=m)
	{
		poz=-1;
		for (k=i; k<=n; k++)
			if (D[k][j])
			{
				poz=k;
				break ;
			}
		if (poz==-1)
		{
			j++;
			continue ;
		}
		if (poz!=i)
			swap_l(i,poz);
		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][m+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();
	solve();
	return 0;
}