Pagini recente » Cod sursa (job #1079278) | Cod sursa (job #2870747) | Cod sursa (job #1082634) | Cod sursa (job #1239562)
#include<fstream>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<cmath>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream in("laser.in");
ofstream out("laser.out");
const int Nmax = 520;
const double PI = 2.0*asin(1);
struct point{
int x,y,ind;
point(){}
point(int _x,int _y,int _ind){x=_x,y=_y,ind=_ind;}
} v[3*Nmax];
int cp(point A,point B,point C){return A.x*B.y - A.y*B.x + B.x*C.y - B.y*C.x + C.x*A.y - C.y*A.x;}
struct cmpA{inline bool operator()(const point &a,const point &b){return a.y<b.y;}};
struct cmpB{inline bool operator()(const point &a,const point &b){return cp(point(0,0,0),a,b) < 0;}};
bitset<Nmax> B,S[3*Nmax];
bitset<3*Nmax> V[Nmax]; //SIZE 2*Nmax
int N,K,n,m,To[3*Nmax],Tip[3*Nmax];
int srch(int ind){
for(int i=1;i<=m;i++) if(V[ind][i]) return i;
return m+2;
}
double angle(point A){
double d=sqrt( A.x*A.x + A.y*A.y );
double ung = abs( acos( double(A.x)/d ) );
if(A.y<0) ung += 2*(PI-ung);
return ung;
}
int main(){
in>>N;
for(int i=1;i<=N;i++){
int x,y;
in>>x>>y;
v[i]=point(x,y,i);
in>>x>>y;
v[N+i]=point(x,y,i);
}
sort(v+1,v+2*N+1,cmpA());
int sep=2*N+1;
for(int i=1;i<=2*N;i++) if(sep>2*N && v[i].y>0) sep=i;
sort(v+1,v+sep,cmpB());
sort(v+sep,v+2*N+1,cmpB());
v[2*N+1]=v[1];
for(int i=1;i<=2*N;i++){
if(!Tip[v[i].ind]) Tip[v[i].ind]=i;
else{
To[i]=Tip[v[i].ind];
To[Tip[v[i].ind]]=i;
}
}
for(int i=1;i<=2*N;i++) Tip[i]=( cp(point(0,0,0),v[i],v[To[i]])<0 );
for(int i=1;i<=2*N;i++) B[v[i].ind]=Tip[i];
for(int i=1;i<=2*N;i++) B[v[i].ind]=Tip[i], S[i]=B;
for(int i=1;i<=N;i++){
int x;
in>>x;
S[2*N+1][i]=x;
}
n=N,m=2*N;
for(int i=1;i<=N;i++){
for(int j=1;j<=2*N;j++) V[i][j]=S[j][i];
V[i][m+1]=S[2*N+1][i];
}
int pos[Nmax],ans[3*Nmax];
memset(ans,0,sizeof(ans));
for(int row=1;row<=n;row++){
int ind=row;
pos[row]=srch(row);
for(int i=row;i<=n;i++){
int p=srch(i);
if(p<pos[row]) pos[row]=p,ind=i;
}
swap(V[row],V[ind]);
for(int i=row+1;i<=n;i++) if(V[i][pos[row]]) V[i]^=V[row];
}
for(int i=1;i<=n;i++){
int s=0;
for(int j=pos[i]+1;j<=m;j++) s^=V[i][j]*ans[j];
ans[pos[i]]=s^V[i][m+1];
}
for(int i=1;i<=m;i++) ans[0]+=ans[i];
out<<ans[0]<<'\n';
for(int i=1;i<=2*N;i++){
if(ans[i]){
double angA = angle(v[i]);
double angB = angle(v[i+1]);
angA=(angA+angB)/2.;
angA=angA/(2*PI)*360.;
out.precision(6);
out<<fixed<<angA<<'\n';
}
}
return 0;
}