Cod sursa(job #721751)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 24 martie 2012 02:22:54
Problema Laser Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define nmax 520
#define PI 3.14159265
#define eps 1e-6

struct dreapta
{
	double x1, y1, x2, y2, t1, t2;
	int c1, c2;
} d[nmax];
	
struct punct
{
	double t;
	int c, p;
} v[2*nmax];

int n, h, a[nmax][2*nmax], l, sol[2*nmax], poz[nmax];

int cadran (double x, double y)
{
	if (x>=0)
	{
		if (y>=0) return 1;
		return 4;
	}
	if (y>=0) return 2;
	return 3;
}

int cmp (punct a, punct b)
{ 
	return a.t < b.t;
}

void gauss ()
{
	int i, j, k, c, ok;
	for (j=1, c=1; j<=h ; j++)
	{
		ok=0;
		for (i=c; i<=n; i++) 
			if (a[i][j]) 
			{
				ok=1;
				break;
			}
		if (!ok) continue;
		if (i!=c)
			for (k=1; k<=h+1; k++) swap (a[i][k], a[c][k]);
		poz[c] = j;
		for (i=c+1; i<=n; i++)
			if (a[i][j])
			{
				for (k=1; k<=h+1; k++) 
					a[i][k] ^= a[c][k];
			}
		c++;
	}
}

int main()
{
	freopen ("laser.in", "r", stdin);
	freopen ("laser.out", "w", stdout);
	scanf ("%d", &n);
	int i, j;
	double x;
	for (i=1; i<=n; i++)
	{
		scanf ("%lf %lf %lf %lf", &d[i].x1, &d[i].y1, &d[i].x2, &d[i].y2);
		v[++h].c = cadran (d[i].x1, d[i].y1);
		v[h].t = atan2 (d[i].y1, d[i].x1) *180.000000 / PI;
		v[h].p = i;
		if (v[h].t < 0) v[h].t += 360.000000;
		d[i].t1 = v[h].t;
		d[i].c1 = v[h].c;
		v[++h].c = cadran (d[i].x2, d[i]. y2);
		v[h].t = atan2 (d[i].y2, d[i].x2) *180.000000 / PI;
		v[h].p = i;
		if (v[h].t < 0) v[h].t += 360.000000;
		d[i].t2 = v[h].t;
		d[i].c2 = v[h].c;
		if (d[i].t1 > d[i].t2)
		{
			swap (d[i].t1, d[i].t2);
			swap (d[i].x1, d[i].x2);
			swap (d[i].y1, d[i].y2);
			swap (d[i].c1, d[i].c2);
		}
	}
	sort (v+1, v+h+1, cmp);
	x = v[1].t;
	for (i=1; i<h; i++) v[i].t = (v[i].t + v[i+1].t)/2;
	v[h].t = (v[h].t + x + 360.000000)*0.5;
	if (v[h].t >= 360.000000) v[h].t -= 360.000000;
	for (i=1; i<=h; i++)
		for (j=1; j <= n; j++)
		{
			if (d[j].c1 == 1 && d[j].t2 > 180.000000 + d[j].t1)
			{
				if (v[i].t >= d[j].t2-eps || v[i].t <= d[j].t1+eps) a[j][i] = 1;
			} else
				if (v[i].t >= d[j].t1-eps && v[i].t <=d[j].t2+eps) a[j][i] = 1;
		}
	for (i=1; i<=n; i++)
		scanf ("%d", &a[i][h+1]);
	gauss();
	
	for (i=n; i>0; i--)
	{
		for (j=poz[i]+1; j<=h; j++) 
			if (sol[j] && a[i][j]) a[i][h+1] = 1 - a[i][h+1];
		if (a[i][h+1]) 
		{
			l++;
			sol[poz[i]] = 1;
		}
	}
	printf ("%d\n", l);
	for (i=1; i<=h; i++) 
		if (sol[i]) printf("%.6lf\n", v[i].t);
}