Pagini recente » Cod sursa (job #1760952) | Cod sursa (job #1193556) | Cod sursa (job #3248979) | Cod sursa (job #2108069) | Cod sursa (job #721736)
Cod sursa(job #721736)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define nmax 520
#define PI 3.14159265
struct dreapta
{
double x1, y1, x2, y2, t1, t2;
int c1, c2;
} d[nmax];
struct punct
{
double t;
int c, p;
} v[2*nmax];
int n, h, a[nmax][2*nmax], l, sol[2*nmax], poz[nmax];
int cadran (double x, double y)
{
if (x>=0)
{
if (y>=0) return 1;
return 4;
}
if (y>=0) return 2;
return 3;
}
int cmp (punct a, punct b)
{
return a.t < b.t;
}
void gauss ()
{
int i, j, k, c, ok;
for (j=1, c=1; j<=h && c<=n; j++)
{
ok=0;
for (i=c; i<=n; i++)
if (a[i][j])
{
ok=1;
break;
}
if (i!=c)
for (k=1; k<=h+1; k++) swap (a[i][k], a[c][k]);
poz[c] = j;
for (i=1; i<=n; i++)
if (i!=j)
if (a[i][j])
for (k=1; k<=h+1; k++)
a[i][k] ^= a[j][k];
if (ok) c++;
}
}
int main()
{
freopen ("laser.in", "r", stdin);
freopen ("laser.out", "w", stdout);
scanf ("%d", &n);
int i, j;
double x;
for (i=1; i<=n; i++)
{
scanf ("%lf %lf %lf %lf", &d[i].x1, &d[i].y1, &d[i].x2, &d[i].y2);
v[++h].c = cadran (d[i].x1, d[i].y1);
v[h].t = atan2 (d[i].y1, d[i].x1) *180 / PI;
v[h].p = i;
if (v[h].t < 0) v[h].t += 360;
d[i].t1 = v[h].t;
d[i].c1 = v[h].c;
v[++h].c = cadran (d[i].x2, d[i]. y2);
v[h].t = atan2 (d[i].y2, d[i].x2) *180 / PI;
v[h].p = i;
if (v[h].t < 0) v[h].t += 360;
d[i].t2 = v[h].t;
d[i].c2 = v[h].c;
if (d[i].t1 > d[i].t2)
{
swap (d[i].t1, d[i].t2);
swap (d[i].x1, d[i].x2);
swap (d[i].y1, d[i].y2);
swap (d[i].c1, d[i].c2);
}
}
sort (v+1, v+h+1, cmp);
x = v[1].t;
for (i=1; i<h; i++) v[i].t = (v[i].t + v[i+1].t)/2;
v[h].t = (v[h].t + x + 360)/2;
if (v[h].t > 360) v[h].t -= 360;
for (j=1; j <= n; j++)
for (i=1; i<=h; i++)
{
if (d[j].c1 == 1 && d[j].t2 > 180 + d[j].t1)
{
if (v[i].t > d[j].t2 || v[i].t < d[j].t1) a[j][i] = 1;
} else
if (v[i].t >= d[j].t1 && v[i].t <=d[j].t2) a[j][i] = 1;
}
for (i=1; i<=n; i++)
scanf ("%d", &a[i][h+1]);
gauss();
for (i=n; i>0; i--)
{
for (j=poz[i]+1; j<=h; j++)
if (sol[j] && a[i][j]) a[i][h+1] = 1 - a[i][h+1];
if (a[i][h+1])
{
l++;
sol[poz[i]] = 1;
}
}
printf ("%d\n", l);
for (i=1; i<=h; i++)
if (sol[i]) printf("%lf\n", v[i].t);
}