Cod sursa(job #53091)

Utilizator alextheroTandrau Alexandru alexthero Data 20 aprilie 2007 22:16:21
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <stdio.h>
#include <math.h>

#define inf (int)1e9
#define nmax 1050

int sx[nmax],sy[nmax],fx[nmax],fy[nmax],X[nmax],Y[nmax],n,i,j,k,N,P[nmax],b[nmax],rv[nmax];
double a1,b1,c1,a2,b2,c2,rx,ry,det;
short int a[nmax][nmax];

inline double min(double i,double j) {
	if(i > j) return j;
	else return i;
}

inline double max(double i,double j) {
	if(i > j) return i;
	else return j;
}

inline int cadran(double x1,double y1) {
	if(x1 == 0 && y1 == 0) return 0;
	else if(x1 >= 0 && y1 >= 0) return 1;
	else if(x1 >= 0 && y1 < 0) return 4;
	else if(x1 < 0 && y1 < 0) return 3;
	else return 2;
}

int apartine(double x1,double y1,int i) {
	if(x1 > max(sx[i],fx[i])) return 0;
	if(x1 < min(sx[i],fx[i])) return 0;
	if(y1 > max(sy[i],fy[i])) return 0;
	if(y1 < min(sy[i],fy[i])) return 0;
	return 1;
}

int intersect(int i,int j) {
	a1 = fy[i] - sy[i];
	b1 = sx[i] - fx[i];
	c1 = sx[i] * a1 + sy[i] * b1;
	a2 = Y[j];
	b2 = -X[j];
	c2 = 0;
	det = (b1 * a2 - b2 * a1);
	if(det == 0) return 0;
	else {
		ry = (double)(c1 * a2 - c2 * a1) / det;
		rx = (double)(c1 * b2 - b1 * c2) / (a1 * b2 - b1 * a2);
		if(cadran(rx,ry) == cadran(X[j],Y[j]) || cadran(rx,ry) == 0 || cadran(X[j],Y[j]) == 0) {
			if(apartine(rx,ry,i)) return 1;
			else return 0;
		}
		else return 0;
	}
}

double unghi(double x1,double y1) {
	int cad = cadran(x1,y1);
	if(cad <= 2) return atan2(y1,x1) * 180 / M_PI;
	else return 360 + atan2(y1,x1) * 180 / M_PI;
}

int main() {
	freopen("laser.in","r",stdin);
	freopen("laser.out","w",stdout);

	scanf("%d",&n);
	for(i = 1; i <= n; i++) scanf("%d%d%d%d",&sx[i],&sy[i],&fx[i],&fy[i]);
	for(i = 1; i <= n; i++) scanf("%d",&b[i]);

	N = 0;
	for(i = 1; i <= n; i++) {
		if(sx[i] != 0 || sy[i] != 0) {
			N++; X[N] = sx[i]; Y[N] = sy[i];
		}
		if(fx[i] != 0 || fy[i] != 0) {
			N++; X[N] = fx[i]; Y[N] = fy[i];
		}
	}

	for(i = 1; i <= n; i++) 
		for(j = 1; j <= N; j++) a[i][j] = intersect(i,j);

	for(i = 1; i <= n; i++) P[i] = i;

	int crt = 0;
	for(i = 1; i <= n; i++) {
		crt++;
		if(a[P[i]][crt] == 0) {
			for(j = i + 1; j <= n; j++)
				if(a[P[j]][crt] == 1) {
					P[i] ^= P[j] ^= P[i] ^= P[j];
					break;
				}
			if(a[P[i]][crt] == 0) {
				i--;
				continue;
			}
		}
		for(j = i + 1; j <= n; j++) 
			if(a[P[j]][crt] == 1) {
				for(k = crt; k <= N; k++) 
					a[P[j]][k] ^= a[P[i]][k];
				b[P[j]] ^= b[P[i]];
			}
	}
	
	int tot,stanga;
	for(i = 1; i <= N; i++) rv[i] = 0;
	for(i = n; i >= 1; i--) {
		tot = 0,stanga = inf;
		for(j = 1; j <= N; j++)
			if(a[P[i]][j] == 1) {
				if(rv[j]) tot++;
				if(tot > 1) tot -= 2;
				stanga = (int)min(stanga,j);
			}
		if(stanga == inf) stanga = 0;
		if(tot != b[P[i]]) rv[stanga] = 1;
	}
	
	tot = 0;
	for(i = 1; i <= N; i++) 
		if(rv[i]) tot++;

	printf("%d\n",tot);
	for(i = 1; i <= N; i++)
		if(rv[i]) printf("%.6lf\n",unghi(X[i],Y[i]));

	

	return 0;
}