Pagini recente » Cod sursa (job #624254) | Cod sursa (job #1920794) | Cod sursa (job #2716752) | Cod sursa (job #2287434) | Cod sursa (job #2086333)
#include <bits/stdc++.h>
#define eps 1e-10
using namespace std;
int mat[1030][1030];
int n;
struct Punct
{
Punct* p;
int x, y;
double alfa;
void calcAlfa()
{
alfa = atan2(y, x);
alfa *= 180. / 3.14159265358979323846264338327950288;
if(alfa < 0)
alfa += 360;
}
bool operator<(const Punct& o) const
{
return alfa < o.alfa;
}
bool intersect(double beta) const
{
double alfaMin = min(alfa, p->alfa);
double alfaMax = max(alfa, p->alfa);
if(alfaMax - alfaMin < 180)
return alfaMin <= beta && beta <= alfaMax;
return alfaMin >= beta || alfaMax <= beta;
}
} v[1030], po[1030];
Punct* d[520];
double unghiuri[1030];
int rez[1030];
int main()
{
freopen("laser.in", "r", stdin);
freopen("laser.out", "w", stdout);
scanf("%d", &n);
const int n2 = n * 2;
for(int i = 0; i < n; i++)
{
scanf("%d%d%d%d", &po[i * 2 + 0].x, &po[i * 2 + 0].y, &po[i * 2 + 1].x, &po[i * 2 + 1].y);
po[i * 2 + 0].calcAlfa();
po[i * 2 + 1].calcAlfa();
po[i * 2 + 0].p = &po[i * 2 + 1];
po[i * 2 + 1].p = &po[i * 2 + 0];
d[i] = &po[i * 2 + 0];
v[i * 2 + 0] = po[i * 2 + 0];
v[i * 2 + 1] = po[i * 2 + 1];
}
for(int i = 0; i < n; i++)
scanf("%d", &mat[i][n2]);
sort(v, v + n * 2);
for(int i = 0; i < n2 - 1; i++)
{
double alfa = (v[i].alfa + v[i + 1].alfa) / 2.;
unghiuri[i] = alfa;
for(int j = 0; j < n; j++)
{
if(d[j]->intersect(alfa))
mat[j][i] = 1;
else mat[j][i] = 0;
}
}
double alfa = (360 - v[n2 - 1].alfa - v[0].alfa) / 2.;
if(alfa < 0)
alfa += 360;
unghiuri[n2 - 1] = alfa;
for(int j = 0; j < n; j++)
{
if(d[j]->intersect(alfa))
mat[j][n2 - 1] = 1;
else mat[j][n2 - 1] = 0;
}
int lc = 0, cc = 0;
while(lc < n && cc < n2)
{
int k = lc;
while(mat[k][cc] == 0 && k < n) k++;
if(k == n)
{
cc++;
continue;
}
if(k != lc)
for(int i = cc; i <= n2; i++)
swap(mat[lc][i], mat[k][i]);
for(int i = lc + 1; i < n; i++)
{
for(int j = cc + 1; j <= n2; j++)
mat[i][j] ^= mat[i][cc] & mat[lc][j];
mat[i][cc] = 0;
}
lc++; cc++;
}
int nrez = 0;
for(int i = lc - 1; i >= 0; i--)
{
int j = 0;
for(; j < n2 && mat[i][j] == 0; j++);
if(j != n2)
{
int x = j;
int rest = 0;
for(j++; j < n2; j++)
rest ^= mat[i][j] & rez[j];
rez[x] = rest ^ mat[i][n2];
if(rez[x] == 1) nrez++;
}
}
printf("%d\n", nrez);
for(int i = 0; i < n2; i++)
if(rez[i] == 1)
printf("%.6f\n", unghiuri[i]);
return 0;
}