Cod sursa(job #49654)

Utilizator gcosminGheorghe Cosmin gcosmin Data 6 aprilie 2007 10:49:25
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <bitset>
using namespace std;

#define NMAX 550
#define eps 1e-6
#define DIST 30000

const double pi = acos(-1);

int N;

double xx[NMAX];
double yy[NMAX];
double xx1[NMAX];
double yy1[NMAX];

int nunghi;
double unghi[NMAX * 2];

int nrez;
double rez[NMAX * 2];

int jeg[NMAX];

bitset <2 * NMAX> a[NMAX];

inline double DABS(double x) { return (x < 0) ? -x : x; }

inline int semn(double x, double y, double x1, double y1, double x2, double y2)
{
	double q = x * (y1 - y2) - y * (x1 - x2) + x1 * y2 - y1 * x2;
	
	if (DABS(q) < eps) return 0;
	if (q < 0) return -1;
	return 1;
}

void make_bitset(int q, double unghi)
{
	double sn = sin(unghi), cs = cos(unghi);

	double x = DIST * cs, y = DIST * sn;

	int e1, e2;

	for (int i = 1; i <= N; i++) {
		e1 = semn(0, 0, xx[i], yy[i], xx1[i], yy1[i]) * semn(x, y, xx[i], yy[i], xx1[i], yy1[i]);
		e2 = semn(xx[i], yy[i], 0, 0, x, y) * semn(xx1[i], yy1[i], 0, 0, x, y);

		if (e1 == 1 || e2 == 1) continue;

		a[i][q] = 1;
	}
}

int main()
{
	int i, x, y, x1, y1;
	double u1, u2;
	
	freopen("laser.in", "r", stdin);
	freopen("laser.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= N; i++) {
		scanf("%d %d %d %d", &x, &y, &x1, &y1);
		xx[i] = x; yy[i] = y;
		xx1[i] = x1; yy1[i] = y1;

		u1 = atan2(y, x); if (y < 0) u1 += 2 * pi;
		u2 = atan2(y1, x1); if (y1 < 0) u2 += 2 * pi;

		unghi[++nunghi] = u1;
		unghi[++nunghi] = u2;

//		printf("%lf %lf\n", u1, u2);
	}
//	printf("\n");

	sort(unghi + 1, unghi + nunghi + 1);

	unghi[nunghi + 1] = -unghi[nunghi];

	for (i = 1; i <= nunghi; i++) make_bitset(i, ( unghi[i] + unghi[i + 1] ) * 0.5);

//	for (i = 1; i <= nunghi; i++) printf("%lf (%g, %g) | ", (unghi[i] + unghi[i+1]) * 0.5, unghi[i], unghi[i+1]);
//	printf("\n");
		
	int w, k, j;
	for (i = 1; i <= N; i++) {
		scanf("%d", &w);
		a[i][2 * N + 1] = w;
	}
	
/*	for (i = 1; i <= N; i++) {
		for (j = 1; j <= 2 * N + 1; j++) printf("%d ", a[i][j] == 1);
		printf("\n");
	}
	printf("\n");
*/
	bitset <2 * NMAX> aux;
	
	for (i = 1, j = 1; i <= 2 * N && j <= N; i++) {
		for (k = j; k <= N && !a[k][i]; k++);

		if (k == N + 1) continue;

		aux = a[j];
		a[j] = a[k];
		a[k] = aux;

		for (k = 1; k <= N; k++) {
			if (k == j || !a[k][i]) continue;

			a[k] ^= a[j];
		}

/*		for (int ii = 1; ii <= N; ii++) {
			for (int jj = 1; jj <= 2 * N + 1; jj++) printf("%d ", a[ii][jj] == 1);
			printf("\n");
		}
		printf("\n");
*/

		jeg[++jeg[0]] = i;
		
		j++;
	}

	int q;
	for (i = 1; i <= jeg[0]; i++) {
		q = jeg[i];
//		printf("-- %d\n", q);
		if (a[i][2 * N + 1]) rez[++nrez] = (unghi[q] + unghi[q + 1]) * 0.5;
	}

	printf("%d\n", nrez);
	for (i = 1; i <= nrez; i++) printf("%lf\n", rez[i] / pi * 180);

fclose(stdin);
fclose(stdout);
return 0;
}