Cod sursa(job #721736)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 24 martie 2012 00:50:14
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define nmax 520
#define PI 3.14159265

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 && c<=n; j++)
	{
		ok=0;
		for (i=c; i<=n; i++) 
			if (a[i][j]) 
			{
				ok=1;
				break;
			}
		if (i!=c)
			for (k=1; k<=h+1; k++) swap (a[i][k], a[c][k]);
		poz[c] = j;
		for (i=1; i<=n; i++)
			if (i!=j)
			if (a[i][j])
				for (k=1; k<=h+1; k++) 
					a[i][k] ^= a[j][k];
		if (ok) 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 / PI;
		v[h].p = i;
		if (v[h].t < 0) v[h].t += 360;
		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 / PI;
		v[h].p = i;
		if (v[h].t < 0) v[h].t += 360;
		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)/2;
	if (v[h].t > 360) v[h].t -= 360;
		for (j=1; j <= n; j++)
	for (i=1; i<=h; i++)
		{
			if (d[j].c1 == 1 && d[j].t2 > 180 + d[j].t1)
			{
				if (v[i].t > d[j].t2 || v[i].t < d[j].t1) a[j][i] = 1;
			} else
				if (v[i].t >= d[j].t1 && v[i].t <=d[j].t2) 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("%lf\n", v[i].t);
}