Pagini recente » Monitorul de evaluare | Cod sursa (job #3282040) | Diferente pentru utilizator/stargold2 intre reviziile 110 si 275 | Profil unu_bun | Cod sursa (job #1694848)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <bitset>
using namespace std;
const int NMAX = 553;
const int LMAX = 2055;
const double MIN_ANGLE = 0;
const double MAX_ANGLE = 360.0;
const double EPS = 1e-10;
struct pt {
double x, y;
};
struct segment {
pt a, b;
double fromAngle, toAngle;
};
int N, M, state[NMAX];
segment A[NMAX];
double candidates[LMAX];
bitset<LMAX> G[NMAX], res;
inline double angle(pt& p) {
double atanV = atan2(p.y, p.x);
atanV = atanV >= 0 ? atanV : (2 * M_PI + atanV);
return atanV * MAX_ANGLE / (2 * M_PI);
}
void read() {
scanf("%d", &N);
double x1, y1, x2, y2;
for (int i = 1; i <= N; i++) {
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
A[i] = {{x1, y1}, {x2, y2}};
A[i].fromAngle = angle(A[i].a);
A[i].toAngle = angle(A[i].b);
if (A[i].fromAngle > A[i].toAngle) {
swap(A[i].fromAngle, A[i].toAngle);
}
}
for (int i = 1; i <= N; i++) {
scanf("%d", &state[i]);
}
}
void prepare() {
vector<double> endPoints;
for (int i = 1; i <= N; i++) {
endPoints.push_back(A[i].fromAngle + EPS);
endPoints.push_back(A[i].toAngle - EPS);
}
endPoints.push_back(MIN_ANGLE);
endPoints.push_back(MAX_ANGLE);
sort(endPoints.begin(), endPoints.end());
for (size_t i = 0; i < endPoints.size(); i++) {
candidates[++M] = endPoints[i];
if (i < endPoints.size() - 1) {
candidates[++M] = (endPoints[i] + endPoints[i + 1]) / 2;
}
}
sort(candidates + 1, candidates + M + 1);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (A[i].toAngle - A[i].fromAngle <= 180.0 + EPS) {
G[i][j] = A[i].fromAngle - EPS <= candidates[j] &&
candidates[j] <= A[i].toAngle + EPS;
} else {
G[i][j] = A[i].toAngle - EPS <= candidates[j] ||
A[i].fromAngle + EPS >= candidates[j];
}
}
G[i][M + 1] = state[i];
}
}
void solve() {
int i = 1, j = 1;
while (i <= N) {
if (!G[i][j]) {
int replacementLine = -1;
for (int k = i + 1; k <= N; k++) {
if (G[k][j]) {
replacementLine = k;
break ;
}
}
if (replacementLine == -1) {
j++;
continue ;
}
swap(G[i], G[replacementLine]);
}
for (int k = i + 1; k <= N; k++) {
if (G[k][j]) {
G[k] ^= G[i];
}
}
i++; j++;
}
for (int i = N; i >= 1; i--) {
if (G[i][M + 1]) {
for (int j = M; j >= 1; j--) {
if (G[i][j]) {
res[j] = G[i][M + 1];
for (int k = i - 1; k >= 1; k--) {
if (G[k][j]) {
G[k] ^= G[i];
}
}
break ;
}
}
}
}
vector<double> sol;
for (int i = 1; i <= M; i++) {
if (res[i]) {
sol.push_back(candidates[i]);
}
}
printf("%d\n", (int)sol.size());
for (auto& ang: sol) {
printf("%.6lf\n", ang);
}
}
int main() {
freopen("laser.in", "r", stdin);
freopen("laser.out", "w", stdout);
read();
prepare();
solve();
return 0;
}