Pagini recente » Cod sursa (job #1580234) | Cod sursa (job #2333119) | Cod sursa (job #986219) | Cod sursa (job #508475) | Cod sursa (job #42608)
Cod sursa(job #42608)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define Nmax 1030
#define pct pair<int, int>
#define x first
#define y second
const double eps = 1.0e-12;
int n;
pct punct[Nmax];
double pan[Nmax], p[Nmax];
int mat[Nmax][Nmax], b[Nmax], v[Nmax];
double nrml(double a)
{
while (a < 0)
a += 360;
while (a > 360)
a -= 360;
return a;
}
void citire()
{
int i;
scanf("%d", &n);
for (i = 1; i <= n; ++i)
scanf("%d %d %d %d", &punct[i].x, &punct[i].y, &punct[i + n].x, &punct[i + n].y);
for (i = 1; i <= n; ++i)
scanf("%d", &b[i]);
for (i = 1; i <= 2*n; ++i)
p[i] = nrml(atan2(punct[i].y, punct[i].x) * 180 / M_PI);
sort(p + 1, p + 2*n + 1);
for (i = 1; i <= 2*n - 1; ++i)
pan[i] = nrml((p[i] + p[i + 1]) / 2);
pan[2*n] = nrml((360 + p[1] + p[2*n]) / 2);
sort(pan+1, pan+2*n+1);
}
int intersect(double x1, double y1, double x2, double y2, double x3, double y3)
{
double p1 = x2 * y1 - x1 * y2;
double p2 = x3 * y1 - x1 * y3;
if (p1 * p2 > - eps)
return 0;
x3 -= x2;
y3 -= y2;
x1 -= x2;
y1 -= y2;
x2 = -x2;
y2 = -y2;
p1 = x2 * y3 - x3 * y2;
p2 = x1 * y3 - x3 * y1;
if (p1 * p2 < - eps)
return 1;
return 0;
}
void gauss()
{
int i, j, k, piv;
piv = 1;
for (i = 1; i <= 2 * n; ++i)
{
for (j = piv; j <= n; ++j)
if (mat[j][i] == 1)
break;
if (i != j && mat[j][i] == 1)
{
for (k = 1; k <= 2 * n; ++k)
swap(mat[piv][k], mat[j][k]);
swap(b[piv], b[j]);
}
if (mat[piv][i] == 0)
continue;
for (j = 1; j <= n; ++j)
if (piv != j && mat[j][i] == 1)
{
for (k = 1; k <= 2 * n; ++k)
mat[j][k] ^= mat[piv][k];
b[j] ^= b[piv];
}
++piv;
}
}
void solve()
{
int i, j, ct = 0;
double x1, y1;
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= 2 * n; ++j)
{
x1 = cos(pan[j] * M_PI / 180) * 50000;
y1 = sin(pan[j] * M_PI / 180) * 50000;
if (intersect(x1, y1, punct[i].x, punct[i].y, punct[i+n].x, punct[i+n].y))
mat[i][j] = 1;
else
mat[i][j] = 0;
}
}
gauss();
for (i = 1; i <= n; ++i)
for (j = 1; j <= 2 * n; ++j)
if (mat[i][j] == 1)
{
v[j] = b[i];
break;
}
for (i = 1; i <= 2 * n; ++i)
if (v[i]) ++ct;
printf("%d\n", ct);
for (i = 1; i <= 2 * n; ++i)
if (v[i])
printf("%.6lf\n", pan[i]);
}
int main()
{
freopen("laser.in", "r", stdin);
freopen("laser.out", "w", stdout);
citire();
solve();
return 0;
}