Cod sursa(job #52788)

Utilizator alextheroTandrau Alexandru alexthero Data 19 aprilie 2007 22:19:05
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <stdio.h>
#include <math.h>

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

int sx[nmax],sy[nmax],fx[nmax],fy[nmax],b[nmax],tryx[2 * nmax],tryy[2 * nmax],tryn,n,i,j;
int a1,b1,c1,a2,b2,c2,det,P[nmax],crt,k,gasit,val[2 * nmax];
double ax,ay;
int a[2 * nmax][nmax];

inline int max(int a,int b) {
	if(a > b) return a;
	else return b;
}

inline int min(int a,int b) {
	if(a > b) return b;
	else return a;
}

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

inline int apartine(double x,double y,int j) {
	if(x > max(fx[j],sx[j])) return 0;
	if(x < min(fx[j],sx[j])) return 0;
	if(y > max(fy[j],sy[j])) return 0;
	if(y < min(fy[j],sy[j])) return 0;
	return 1;
}

int intersect(int x,int y) {
	a1 = fy[x] - sy[x];
	b1 = sx[x] - fx[x];
	c1 = sx[x] * a1 + sy[x] * b1;
	a2 = tryy[y];
	b2 = -tryx[y];
	c2 = 0;
	det = b1 * a2 - b2 * a1;
	if(det == 0) {
		return 0;
	}
	else {
		ay = (double)(c1 * a2 - c2 * a1) / det;
		ax = (double)(c1 * b2 - c2 * b1) / -det;
		if(!apartine(ax,ay,x)) return 0;
		if(cadran(ax,ay) == cadran(tryx[y],tryy[y]) || cadran(tryx[y],tryy[y]) == 0 || cadran(ax,ay) == 0) return 1;
		else return 0;
	}
}

double unghi(double x1,double y1) {
	if(cadran(x1,y1) == 1) return atan2(y1,x1) * 180 / M_PI;
	else if(cadran(x1,y1) == 2) return atan2(y1,x1) * 180 / M_PI;
	else if(cadran(x1,y1) == 3) return 360 + atan2(y1,x1) * 180 / M_PI;
	else if(cadran(x1,y1) == 4) return 360 + atan2(y1,x1) * 180 / M_PI;
	return 0.0;
}

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]);

	for(i = 1; i <= n; i++) {
		tryn++;
		tryx[tryn] = sx[i]; 
		tryy[tryn] = sy[i];
		tryn++;
		tryx[tryn] = fx[i]; 
		tryy[tryn] = fy[i];
	}

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

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

	crt = 0;
	for(i = 1; i <= n; i++) {
		crt++;
		if(a[P[i]][crt] == 0) {
			gasit = 0;
			for(j = i + 1; j <= n; j++)
				if(a[P[j]][crt] != 0) {
					P[i] ^= P[j] ^= P[i] ^= P[j];
					gasit = 1;
				}
			if(!gasit) {
				i--;
				continue;
			}
		}
		for(j = i + 1; j <= n; j++) {
			if(a[P[j]][crt] != 0) { 
				for(k = crt; k <= tryn; k++) 
					a[P[j]][k] ^= a[P[i]][k];
				b[P[j]] -= b[P[i]];
				if(b[P[j]] < 0) b[P[j]] += 2;
			}
		}
	}

	return 0;
	
	for(i = n; i >= 1; i--) {
		int crtval = 0,stanga = inf;
		for(j = 1; j <= tryn; j++) {
			crtval = crtval + a[P[i]][j] * val[j];
			if(crtval >= 2) crtval -= 2;
			if(a[P[i]][j] == 1) stanga = min(stanga,j);
		}
		if(crtval != b[P[i]]) val[stanga] = 1;
	}

	int tot = 0;
	for(i = 1; i <= tryn; i++) tot += val[i];
	printf("%d\n",tot);
	for(i = 1; i <= tryn; i++) 
		if(val[i]) printf("%lf\n",unghi(tryx[i],tryy[i]));

	return 0;
}