Pagini recente » Cod sursa (job #541637) | Cod sursa (job #727714) | Cod sursa (job #2952646) | Cod sursa (job #2584974) | Cod sursa (job #1783334)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN 550
using namespace std;
struct coord
{
double x, y;
coord(double x = 0, double y = 0) : x(x), y(y) { }
};
struct segm
{
coord st, dr;
};
segm a[MAXN];
int n;
int f[MAXN], nq, go[MAXN];
int c[MAXN][2*MAXN], sol[2*MAXN];
double EPS = 0.00001;
double d[2*MAXN];
void read()
{
scanf("%d\n", &n);
for (int i = 1; i <= n; i++)
scanf("%lf %lf %lf %lf", &a[i].st.x, &a[i].st.y, &a[i].dr.x, &a[i].dr.y);
for (int i = 1; i <= n; i++)
scanf("%d ", &f[i]);
}
inline double angle(double x, double y) {
double angle = atan2(y, x) * 180.0 / 3.1415926;
if (angle < 0) angle += 360;
return angle;
}
double build(coord st, coord dr)
{
coord mij = coord((st.x+dr.x)/2, (st.y+dr.y)/2);
return angle(mij.x, mij.y);
}
bool inter(double dt, segm s) /// returns whether dt intersects s
{
double ast = angle(s.st.x, s.st.y);
double adr = angle(s.dr.x, s.dr.y);
if (ast > adr) swap(ast, adr);
if (adr - ast < 180+EPS)
return (ast-EPS < dt && dt < adr+EPS);
return (dt < ast+EPS || dt > adr-EPS);
}
void prepare()
{
a[n+1] = a[1];
for (int i = 1; i <= n; i++) {
d[++nq] = angle(a[i].st.x, a[i].st.y);
d[++nq] = angle(a[i].dr.x, a[i].dr.y);
}
sort(d+1, d+nq+1);
d[nq+1] = d[1];
for (int i = 1; i <= nq; i++) {
if (d[i+1] - d[i] > 180)
d[i] = (d[i] + 360 + d[i+1]) / 2;
d[i] = (d[i] + d[i+1]) / 2;
if (d[i] < 0) d[i] += 360;
if (d[i] > 360) d[i] -= 360;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= nq; j++)
c[i][j] = inter(d[j], a[i]);
c[i][nq+1] = f[i];
}
nq++;
}
void solve()
{
for (int i = 1, j = 1; i <= n && j <= nq; j++) {
int ok = 0;
for (int x = i; x <= n && !ok; x++)
if (c[x][j] != 0) {
for (int p = 1; p <= nq; p++)
swap(c[i][p], c[x][p]);
ok = 1;
}
if (!ok) continue;
for (int ki = i+1; ki <= n; ki++) {
int val = c[ki][j];
for (int kj = j; kj <= nq; kj++)
c[ki][kj] ^= val;
}
go[i] = j;
i++;
}
for (int i = n; i >= 1; i--) {
int sum = 0;
for (int j = go[i]+1; j < nq; j++)
sum ^= (c[i][j] && sol[j]);
sol[go[i]] = sum ^ c[i][nq];
}
}
void afisare()
{
int cnt = 0;
for (int i = 1; i < nq; i++)
if (sol[i]) cnt++;
printf("%d\n", cnt);
for (int i = 1; i < nq; i++)
if (sol[i])
printf("%f\n", d[i]);
}
int main()
{
freopen("laser.in", "r", stdin);
freopen("laser.out", "w", stdout);
read();
prepare();
solve();
afisare();
return 0;
}