Cod sursa(job #728837)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 29 martie 2012 00:15:18
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<bitset>

#define maxn 515

using namespace std;

FILE*f=fopen("laser.in","r");
FILE*g=fopen("laser.out","w");

int n,d;
int sol[maxn<<1];
bitset<maxn<<1>G[maxn],aux;
double drepte[maxn<<1];
const double pi = 3.1415926535897932384626433832795;

struct seg{
	double i1,j1;
	double i2,j2;
}A[maxn];

inline double unghi ( double x , double y ){
	double unghi = atan2(y,x) * 180 / pi;
	if ( unghi < 0 )	unghi += 360;
	return unghi;
}

inline bool equal ( const double &a , const double &b ){
	double dif = a - b;
	if ( dif < 0 ) dif = -dif;
	return dif < (1e-7);
}

inline void swap ( int &a , int &b ){
	int aux = a; a = b; b = aux;
}

inline bool inters ( double x , double u1 , double u2 ){
	double a = min(u1,u2); double b = max(u1,u2);
	
	if ( u1 <= 90 ){
		if ( u2 >= 270 ){
			return (x <= u1 || equal(x,u1)) || (x >= u2 || equal(x,u2));
		}
		return (x >= a || equal(x,a)) && (x <= b || equal(x,b));
	}
	if ( u1 <= 180 ){
		return (x >= a || equal(x,a)) && (x <= b || equal(x,b));
	}
	if ( u1 <= 270 ){
		return (x >= a || equal(x,a)) && (x <= b || equal(x,b));
	}
	if ( u2 <= 90 ){
		return (x <= u2 || equal(x,u2)) || (x >= u1 || equal(x,u1));;
	}
	return (x >= a || equal(x,a)) && (x <= b || equal(x,b));
}

inline void gauss () {
	int i,j,index;
	i = j = 1;
	
	while ( i <= n && j <= d ){
		
		for ( index = i ; index <= n ; ++index ){
			if ( G[index][j] ){
				break ;
			}
		}
		
		if ( index == n + 1 ){
			++j; continue ;
		}
		
		if ( index != i ){
			aux = G[i]; G[i] = G[index]; G[index] = aux;
		}
		
		for ( index = i + 1 ; index <= n ; ++index ){
			if ( G[index][j] ){
				G[index] ^= G[i];
			}
		}
		
		++i; ++j;
	}
	
	for ( i = n ; i >= 1 ; --i ){
		for ( j = 1 ; j <= d ; ++j ){
			if ( G[i][j] ){
				sol[j] = G[i][d+1];
				for ( index = j + 1 ; index <= d ; ++index ){
					if ( G[i][index] )
						sol[i] ^= sol[index];
				}
				break ;
			}
		}
	}
}
	
int main () {
	
	fscanf(f,"%d",&n);
	
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%lf %lf %lf %lf",&A[i].i1,&A[i].j1,&A[i].i2,&A[i].j2);
		drepte[++d] = unghi(A[i].i1,A[i].j1);
		drepte[++d] = unghi(A[i].i2,A[i].j2);
	}
	
	sort(drepte+1,drepte+d+1);
	
	double first = drepte[1];
	for ( int i = 1 ; i < d ; ++i ){
		drepte[i] = (drepte[i]+drepte[i+1])/2;
	}
	drepte[d] = (first + 360 + drepte[d]) / 2;
	if ( drepte[d] > 360 )	drepte[d] -= 360;
	sort(drepte+1,drepte+d+1);
	
	int k = 0;
	for ( int i = 1 ; i <= d ; ++i ){
		if ( i == 1 || !equal(drepte[i],drepte[i-1]) ){
			drepte[++k] = drepte[i];
		}
	}
	d = k;
	
	for ( int i = 1 ; i <= n ; ++i ){
		double u1 = unghi(A[i].i1,A[i].j1);
		double u2 = unghi(A[i].i2,A[i].j2);
		for ( int j = 1 ; j <= d ; ++j ){
			if ( inters(drepte[j],u1,u2) ){
				G[i][j] = 1;
			}
		}
	}
	
	int x;
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d",&x);
		G[i][d+1] = x;
	}
	
	gauss();
	
	int s = 0;
	for ( int i = 1 ; i <= d ; ++i ){
		s += sol[i];
	}
	
	fprintf(g,"%d\n",s);
	for ( int i = 1 ; i <= d ; ++i ){
		if ( sol[i] ){
			fprintf(g,"%lf\n",drepte[i]);
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}