Pagini recente » Cod sursa (job #2580285) | Cod sursa (job #2030505) | Cod sursa (job #2860537) | Cod sursa (job #1135509) | Cod sursa (job #740435)
Cod sursa(job #740435)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;
#define maxn 1550
#define PI 3.14159265
int n, m, ns, f[maxn], c[maxn];
double a[maxn], sol[maxn];
struct neon
{
pair<int, int> p1, p2;
double u1, u2;
} v[maxn];
pair<double, int> q[maxn];
bitset<maxn> g[maxn];
int det(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3)
{
int d = p1.first*p2.second + p2.first*p3.second + p3.first*p1.second
- p2.first*p1.second - p3.first*p2.second - p1.first*p3.second;
if(d>0)
return 1;
if(d<0)
return -1;
return 0;
}
void new_shot(double u)
{
++ns;
a[ns]=u*180/PI;
if(a[ns]<0)
a[ns]+=360;
if(a[ns]>360)
a[ns]-=360;
for(int i=1; i<=n; ++i)
g[i][ns]=f[i];
}
void build_shots()
{
int nq=0;
for(int i=1; i<=n; ++i)
{
if(det(make_pair(0, 0), v[i].p1, v[i].p2)==-1)
swap(v[i].p1, v[i].p2);
v[i].u1=atan2(1.0*v[i].p1.second, 1.0*v[i].p1.first);
v[i].u2=atan2(1.0*v[i].p2.second, 1.0*v[i].p2.first);
if(v[i].u1<0)
v[i].u1+=2*PI;
if(v[i].u2<0)
v[i].u2+=2*PI;
if(v[i].u2<v[i].u1)
f[i]=1;
q[++nq]=make_pair(v[i].u1, i);
q[++nq]=make_pair(v[i].u2, i);
}
sort(q+1, q+nq+1);
for(int i=1; i<=nq; ++i)
{
if(i!=1)
new_shot((q[i].first+q[i-1].first)/2);
f[q[i].second]=1-f[q[i].second];
}
new_shot((q[1].first+q[nq].first-2*PI)/2);
for(int i=1; i<=n; ++i)
g[i][ns+1]=c[i];
}
void solve()
{
int i=1, j=0, l;
while(i<=n && j<ns)
{
for(l=i; l<=n; ++l)
if(g[l][j]!=0)
break;
if(l==n+1)
{
++j;
continue;
}
if(l!=i)
swap(g[l], g[i]);
for(int u=1; u<=n; ++u)
{
if(u==i)
continue;
if(g[u][j]==1)
g[u]^=g[i];
}
++i; ++j;
}
int nsol=0;
for(int i=1; i<=n; ++i)
{
if(g[i][ns+1]==0)
continue;
for(int j=1; j<=ns; ++j)
if(g[i][j]==1)
{
sol[++nsol]=a[j];
break;
}
}
printf("%d\n", nsol);
for(int i=1; i<=nsol; ++i)
printf("%.6lf\n", sol[i]);
}
int main()
{
freopen("laser.in", "r", stdin);
freopen("laser.out", "w", stdout);
scanf("%d", &n);
for(int i=1; i<=n; ++i)
scanf("%d%d%d%d", &v[i].p1.first, &v[i].p1.second, &v[i].p2.first, &v[i].p2.second);
for(int i=1; i<=n; ++i)
scanf("%d", &c[i]);
build_shots();
/* for(int i=1; i<=n; ++i)
{
for(int j=1; j<=ns+1; ++j)
printf("%d ", int(g[i][j]));
printf("\n");
}
for(int i=1; i<=ns; ++i)
printf("%.2lf ", a[i]);
printf("\n");*/
solve();
/* for(int i=1; i<=n; ++i)
{
for(int j=1; j<=ns+1; ++j)
printf("%d ", int(g[i][j]));
printf("\n");
}*/
return 0;
}