Pagini recente » Cod sursa (job #430709) | Cod sursa (job #921765) | Cod sursa (job #320600) | Cod sursa (job #2809331) | Cod sursa (job #324662)
Cod sursa(job #324662)
#include<stdio.h>
#include<math.h>
#include<bitset>
#include<algorithm>
using namespace std;
#define N 520
#define fs first
#define sc second
#define mp make_pair
const double eps=1e-6;
const double pi=3.14159265;
int n,m;
double unghi[N<<1];
double bis[N<<1];
double sol[N<<1];
pair<double,double> seg[N];
bitset<(N<<1)> eq[N],sec;
inline char cmp(double x,double y)
{
if(x+eps<y)
return -1;
if(y+eps<x)
return 1;
return 0;
}
inline double convert(double x,double y)
{
if(x>=0 && y>=0)
{
double ip=sqrt(x*x+y*y);
return acos(x/ip)*180.00000/pi;
}
if(x<=0 && y>=0)
{
if(x!=0)
x=-x;
double ip=sqrt(x*x+y*y);
double aux=acos(x/ip)*180.00000/pi;
return 180.00000-aux;
}
if(x<=0 && y<=0)
{
if(x!=0)
x=-x;
if(y!=0)
y=-y;
double ip=sqrt(x*x+y*y);
double aux=acos(x/ip)*180.00000/pi;
return aux+180.00000;
}
if(y!=0)
y=-y;
double ip=sqrt(x*x+y*y);
double aux=acos(x/ip)*180.00000/pi;
return 360.00000-aux;
}
bool compar(const double &x,const double &y)
{
if(cmp(x,y)==-1)
return true;
return false;
}
inline void citire()
{
scanf("%d",&n);
int aux=-1;
int x1,y1,x2,y2;
double un;
for(int i=0; i<n; ++i)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
un=convert((double)x1,(double)y1);
//if(cmp(un,360.00000)!=-1)
// un-=360.00000;
seg[i].fs=un;
unghi[++aux]=un;
un=convert((double)x2,(double)y2);
//if(cmp(un,360.00000)!=-1)
// un-=360.00000;
seg[i].sc=un;
unghi[++aux]=un;
if(cmp(seg[i].fs,seg[i].sc)==1)
swap(seg[i].fs,seg[i].sc);
}
sort(unghi,unghi+aux+1,compar);
}
inline bool vezi(pair<double,double> s,double un)
{
double aux=s.sc-s.fs;
if(cmp(aux,180.00000)!=1)
{
if(cmp(s.fs,un)!=1 && cmp(un,s.sc)!=1)
return true;
return false;
}
else
{
if(cmp(s.fs,un)==-1 && cmp(un,s.sc)==-1)
return false;
return true;
}
}
inline void make_eq()
{
m=n<<1;
unghi[m]=unghi[0];
if(cmp(unghi[m],unghi[m-1])==-1)
unghi[m]+=360.00000;
for(int i=0; i<m; ++i)
bis[i]=(unghi[i+1]-unghi[i])/2+unghi[i];
if(cmp(bis[m-1],360.00000)!=-1)
bis[m-1]-=360.00000;
int aux;
for(int i=0; i<n; ++i)
{
for(int j=0; j<m; ++j)
{
if(vezi(seg[i],bis[j]))
eq[i][j]=1;
}
scanf("%d",&aux);
if(aux)
eq[i][m]=1;
else
eq[i][m]=0;
}
}
inline void rezolva()
{
int r1;
bitset<(N<<1)> baux;
for(int col=0,rand=0; col<m; ++col)
{
for(r1=rand; r1<n && !eq[r1][col]; ++r1)
;
if(r1==n)
{
sec[col]=1;
continue;
}
if(r1!=rand)
{
baux=eq[rand];
eq[rand]=eq[r1];
eq[r1]=baux;
}
for(int i=rand+1; i<n; ++i)
{
if(eq[i][col])
eq[i]^=eq[rand];
}
++rand;
}
int nrez=0;
for(int i=0; i<m; ++i)
{
if(sec[i])
{
for(int j=0; j<n; ++j)
{
if(eq[j][i])
eq[j][i]=0;
}
}
}
int val;
for(int col=m-1,rand; col>=0; --col)
{
if(sec[col])
continue;
for(rand=n-1; !eq[rand][col] && rand>0; --rand)
;
if(eq[rand][m]==1)
val=1;
else
val=0;
if(val==1)
sol[++nrez]=bis[col];
for(int i=0; i<n; ++i)
{
if(eq[i][col])
{
eq[i][col]=0;
eq[i][m]= val==1 ? !eq[i][m] : eq[i][m];
}
}
}
printf("%d\n",nrez);
for(int i=1; i<=nrez; ++i)
printf("%lf\n",sol[i]);
}
int main()
{
freopen("laser.in","r",stdin);
freopen("laser.out","w",stdout);
citire();
make_eq();
rezolva();
//for(int i=0; i<n; ++i)
// printf("%lf %lf\n",seg[i].fs,seg[i].sc);
//for(int i=0; i<m; ++i)
// printf("%lf ",bis[i]);
//printf("\n");
//for(int i=0; i<m; ++i)
// printf("%lf ",unghi[i]);
//printf("\n");
return 0;
}