Pagini recente » Cod sursa (job #869043) | Cod sursa (job #2732814) | Cod sursa (job #2483700) | Cod sursa (job #319224) | Cod sursa (job #801875)
Cod sursa(job #801875)
#include <cstdio>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <bitset>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int MaxN = 550;
const int MaxP = 1100;
pii P[MaxP];
int N, M, Sol[MaxP];
bitset<MaxP> A[MaxN];
inline int Sign(int a, int b, int c, pii p) {
return a*p.x+b*p.y+c;
}
inline bool Intersect(pii p1, pii p2, int a, int b, int c) {
return Sign(a, b, c, p1)*Sign(a, b, c, p2) <= 0;
}
void BuildSystem() {
for (int i = 0; i < M; ++i) {
int a = P[i].y, b = -P[i].x, c = 0;
for (int j = 0; j < N; ++j)
if (Intersect(P[j], P[j+N], a, b, c))
A[j][i] = 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[0] = -1; return;
}
if (j < M)
Sol[j] = A[i][M];
}
}
void Solve() {
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)
assert(scanf("%d %d %d %d", &P[i].x, &P[i].y, &P[i+N].x, &P[i+N].y) == 4);
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));
if (Sol[0] == -1) {
printf("No solution\n"); return;
}
int n = 0;
for (int i = 0; i < M; ++i)
n += Sol[i];
printf("%d\n", 2*n);
for (int i = 0; i < M; ++i) {
if (Sol[i]) {
double Alpha = 180.0/acos(-1)*atan2(P[i].y, P[i].x);
printf("%.8lf\n%.8lf\n", Alpha, Alpha+180.0 <= 360.0 ? Alpha+180.0 : Alpha-180.0);
}
}
}
int main() {
Read();
Solve();
Print();
return 0;
}