Cod sursa(job #843282)

Utilizator stoicatheoFlirk Navok stoicatheo Data 27 decembrie 2012 18:03:24
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.73 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 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);
    u1 = a; u2 = b;
     
    int c1 = cadran(u1),c2 = cadran(u2);
     
    if ( 360 - u2 + u1 <= 180 ){
        return x <= u1 || equal(x,u1) || x >= u2 || equal(x,u2); 
    }
     
    return equal(u1,x) || equal(u2,x) || (x >= u1 && x <= u2);
}
 
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;
}