Pagini recente » Cod sursa (job #2410100) | Cod sursa (job #1750603) | Cod sursa (job #304085) | Cod sursa (job #1296133) | Cod sursa (job #801914)
Cod sursa(job #801914)
#include <cstdio>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <bitset>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int MaxN = 550;
const int MaxP = 1100;
const double Eps = 1e-10;
pdd Segments[MaxP];
double Alpha[MaxP];
int N, M, Sol[MaxP];
bitset<MaxP> A[MaxN];
inline double GetAlpha(int x, int y) {
double alpha = atan2(y, x)*180.0/acos(-1);
if (alpha < 0.0)
alpha += 360.0;
return alpha;
}
void BuildAlpha() {
for (int i = 0; i < N; ++i)
Alpha[i] = Segments[i].x, Alpha[i+N] = Segments[i].y;
sort(Alpha, Alpha+M);
Alpha[M] = Alpha[0];
for (int i = 0; i < M; ++i) {
Alpha[i] = (Alpha[i]+Alpha[i+1])/2.0;
if (Alpha[i] > 360.0)
Alpha[i] -= 360.0;
}
}
void BuildSystem() {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (Segments[i].y-Segments[i].x < 180.0+Eps) {
if (Segments[i].x-Eps < Alpha[j] && Alpha[j] < Segments[i].y+Eps)
A[i][j] = 1;
}
else {
if ((-Eps < Alpha[j] && Alpha[j] < Segments[i].x+Eps) || (Alpha[j] > 180.0-Eps && Alpha[j] > Segments[i].y))
A[i][j] = 1;
}
}
}
}
void Gauss() {
int i = 0, j = 0;
while (i < N && j < M) {
int k;
for (k = i; k < N && !A[i][j]; ++k);
if (k == N) {
++j; continue;
}
swap(A[i], A[k]);
for (k = 0; k < N; ++k)
if (i != k && A[k][j])
A[k] ^= A[i];
++i, ++j;
}
}
void BuildSol() {
for (int i = 0, j; i < N; ++i) {
for (j = 0; j <= M && !A[i][j]; ++j);
if (j < M)
Sol[j] = A[i][M];
}
}
void Solve() {
BuildAlpha();
BuildSystem();
Gauss();
BuildSol();
}
void Read() {
assert(freopen("laser.in", "r", stdin));
assert(scanf("%d", &N) == 1); M = 2*N;
for (int i = 0; i < N; ++i) {
int x1, y1, x2, y2;
assert(scanf("%d %d %d %d", &x1, &y1, &x2, &y2) == 4);
Segments[i].x = GetAlpha(x1, y1), Segments[i].y = GetAlpha(x2, y2);
if (Segments[i].x > Segments[i].y)
swap(Segments[i].x, Segments[i].y);
}
for (int i = 0; i < N; ++i) {
int C; assert(scanf("%d", &C) == 1);
A[i][M] = C;
}
}
void Print() {
assert(freopen("laser.out", "w", stdout));
int n = 0;
for (int i = 0; i < M; ++i)
n += Sol[i];
printf("%d\n", n);
for (int i = 0; i < M; ++i)
if (Sol[i])
printf("%.8lf\n", Alpha[i]);
}
int main() {
Read();
Solve();
Print();
return 0;
}