Pagini recente » Cod sursa (job #3039055) | Cod sursa (job #1310560) | Cod sursa (job #2318278) | Cod sursa (job #1870920) | Cod sursa (job #728868)
Cod sursa(job #728868)
#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 int cadran ( double u ){
if ( u <= 90 ) return 1;
if ( u <= 180 ) return 2;
if ( u <= 270 ) return 3;
return 4;
}
inline bool inters ( double x , double u1 , double u2 ){
double a = min(u1,u2); double b = max(u1,u2);
int c1 = cadran(u1),c2 = cadran(u2);
if ( c1 == 1 && c2 == 4 ){
if ( x <= u1 || equal(x,u1) ) return 1;
if ( x >= u2 || equal(x,u2) ) return 1;
return 0;
}
if ( c1 == 4 && c2 == 1 ){
if ( x <= u2 || equal(x,u2) ) return 1;
if ( x >= u1 || equal(x,u1) ) return 1;
return 0;
}
return equal(u1,x) || equal(u2,x) || (x >= a && 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[j] ^= 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 - 360 + drepte[d];
if ( drepte[d] < 0 ) 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;
}