Pagini recente » Cod sursa (job #770364) | Cod sursa (job #449698) | Cod sursa (job #3224950) | Cod sursa (job #619655) | Cod sursa (job #41694)
Cod sursa(job #41694)
#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-8;
int n;
pct punct[Nmax];
double pan[Nmax], p[Nmax];
int mat[Nmax][Nmax], b[Nmax], v[Nmax];
double nrml(double a)
{
if (a < 0)
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] = (p[i] + p[i + 1]) / 2 + eps;
pan[2*n] = nrml(360 + p[1] + p[2*n] + eps) / 2;
sort(pan+1, pan+2*n+1);
}
int intersect(double a, double b, double aa, double bb, double cc, double &x0, double &y0)
{
if (fabs(bb) < eps)
{
y0 = a * x0;
return 0;
}
if (fabs(a / b - aa / bb) < eps)
return -1;
x0 = cc / (aa * b - a * bb);
y0 = (a * cc) / (aa * b - a * bb);
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;
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= 2 * n; ++j)
{
double x0, y0;
double a = punct[i].y - punct[i + n].y;
double b = punct[i + n].x - punct[i].x;
double c = punct[i].x * punct[i + n].y - punct[i + n].x * punct[i].y;
x0 = punct[i].x;
y0 = punct[i].y;
if (intersect(tan(pan[j] * M_PI / 180), -1.0, a, b, c, x0, y0) == -1)
mat[i][j] = 0;
else if ((min(punct[i].x, punct[i+n].x) - eps < x0 && x0 < max(punct[i].x, punct[i+n].x) + eps) &&
(min(punct[i].y, punct[i+n].y) - eps < y0 && y0 < max(punct[i].y, punct[i+n].y) + eps))
if (fabs(nrml(atan2(y0, x0) * 180 / M_PI) - pan[j]) < eps)
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;
}