Pagini recente » Cod sursa (job #302228) | Cod sursa (job #2676818) | Cod sursa (job #1296146) | Cod sursa (job #962774) | Cod sursa (job #1736241)
#include <bits/stdc++.h>
#define maxN 515
#define e 0.0000001
using namespace std;
int n, m, x[maxN * 2], ans;
double sol[maxN * 2];
bitset < maxN > a[2 * maxN];
struct line
{
int x, y;
double d;
} V[2 * maxN];
struct segm
{
line a, b;
} v[maxN];
void Swap(double &x, double &y)
{
double aux;
aux = x;
x = y;
y = aux;
}
double degree(line a)
{
double d = atan2(a.y, a.x) * (180.0 / M_PI);
if (d < 0.0)
d += 360.0;
return d;
}
int cmp(const line a, const line b)
{
double d1 = degree(a), d2 = degree(b);
return d1 < d2;
}
void Gauss()
{
int i = 1, j = 1;
while (i <= n && j <= m)
{
int x, y;
for (x = i; x <= n; ++ x)
if (a[x][j] != 0)
break;
if (x == n + 1)
{
//++ sol;
++ j;
continue;
}
if (x != i)
for (y = 1; y <= m + 1; ++ y)
{
bool bit = a[x][y];
a[x][y] = a[i][y];
a[i][y] = bit;
}
for (y = i + 1; y <= n; ++ y)
if (a[y][j] != 0)
a[y] ^= a[i];
++ i;
++ j;
//++ sol;
}
//sol = m - sol;
}
void Coef()
{
int i, j, y;
for (i = n; i >= 1; -- i)
for (j = 1; j <= m + 1; ++ j)
if (a[i][j] != 0)
{
/* No solution...
if (j == m + 1)
{
ans = -1;
return ;
}*/
x[j] = a[i][m + 1];
for (y = j + 1; y <= m; ++ y)
x[j] -= (a[i][y] != 0) * x[y];
if (x[j])
sol[++ ans] = V[j].d;
break;
}
}
void read()
{
int i;
freopen("laser.in", "r", stdin);
scanf("%d", &n);
for (i = 1; i <= n; ++ i)
{
scanf("%d %d %d %d", &v[i].a.x, &v[i].a.y, &v[i].b.x, &v[i].b.y);
V[++ m].x = v[i].a.x;
V[m].y = v[i].a.y;
V[++ m].x = v[i].b.x;
V[m].y = v[i].b.y;
}
for (i = 1; i <= n; ++ i)
{
bool st;
scanf("%d", &st);
a[i][m + 1] = st;
}
}
bool intersects(int i, int j)
{
double d1 = degree(v[i].a), d2 = degree(v[i].b), d = V[j].d;
bool ok = 0;
if (d1 > d2)
Swap(d1, d2);
if (d1 <= d + e && d <= d2 + e)
ok = 1;
if (d2 - d1 > 180.0 + e)
return !ok;
return ok;
}
void solve()
{
int i, j;
sort(V + 1, V + m + 1, cmp);
V[m + 1] = V[1];
for (i = 1; i <= m; ++ i)
{
V[i].d = (degree(V[i]) + degree(V[i + 1]) + 360 * (i == m)) / 2.0;
if (V[i].d > 360)
V[i].d -= 360;
}
for (i = 1; i <= n; ++ i)
for (j = 1; j <= m; ++ j)
if (intersects(i, j))
a[i][j] = 1;
Gauss();
Coef();
}
void write()
{
int i;
freopen("laser.out", "w", stdout);
printf("%d\n", ans);
sort(sol + 1, sol + ans + 1);
for (i = 1; i <= ans; ++ i)
printf("%.6lf\n", sol[i]);
}
int main()
{
read();
solve();
write();
return 0;
}