Pagini recente » Cod sursa (job #2757081) | Cod sursa (job #1599523) | Cod sursa (job #3246212) | Cod sursa (job #955260) | Cod sursa (job #324520)
Cod sursa(job #324520)
#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)
{
return acos(x/(sqrt(x*x+y*y)))*180.00000/pi;
}
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(y1<0)
un+=180.00000;
if(cmp(un,360.00000)!=-1)
un-=360.00000;
seg[i].fs=un;
unghi[++aux]=un;
un=convert((double)x2,(double)y2);
if(y2<0)
un+=180.00000;
if(cmp(un,360.00000)!=-1)
un-=360.00000;
seg[i].sc=un;
unghi[++aux]=un;
}
sort(unghi,unghi+aux+1,compar);
}
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(cmp(seg[i].fs,bis[j])==-1 && cmp(bis[j],seg[i].sc)==-1)
eq[i][j]=1;
}
scanf("%d",&aux);
eq[i][m]= (aux==0) ? 0 : 1;
}
}
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;
}
}
}
bitset<1> val;
for(int col=m-1,rand=n-1; col>=0; --col)
{
if(sec[col])
continue;
for(; !eq[rand][col] && rand>0; --rand)
;
val[0]=eq[rand][m];
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[0]==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();
return 0;
}