Pagini recente » Cod sursa (job #1832417) | Cod sursa (job #1757647) | Cod sursa (job #864948) | Cod sursa (job #2595441) | Cod sursa (job #2429101)
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
struct Point {
int x, y, id;
};
struct Solver {
int n;
vector<int> color;
vector<vector<pair<int, int>>> adj;
Solver(int n) : n(n), color(n + 1, -1), adj(n + 1) {}
void add(int l, int r, int val) {
adj[l].emplace_back(r, val);
adj[r].emplace_back(l, val);
}
bool dfs(int node, int col) {
if (color[node] != -1) {
return color[node] == col;
}
color[node] = col;
bool ret = true;
for (auto &p : adj[node]) {
ret &= dfs(p.first, col ^ p.second);
}
return ret;
}
bool solve() {
for (int i = 0; i < n; ++i) {
if (color[i] == -1) {
if (!dfs(i, 0)) {
return false;
}
}
}
return true;
}
vector<bool> getSol() {
vector<bool> sol(n);
for (int i = 0; i < n; ++i) {
sol[i] = color[i] ^ color[i + 1];
}
return sol;
}
};
int getQuadrant(Point p) {
if (p.x >= 0 && p.y >= 0) return 1;
if (p.x < 0 && p.y >= 0) return 2;
if (p.x < 0 && p.y < 0) return 3;
assert(p.x >= 0 && p.y < 0);
return 4;
}
int det(Point a, Point b, Point c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
const long double PI = acos(-1);
long double getAng(Point p) {
long double ang = atan2(p.y, p.x);
if (ang < 0) ang += 2 * PI;
return ang * 180.0 / PI;
}
int main() {
freopen("laser.in", "r", stdin);
freopen("laser.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.precision(8);
cout << fixed;
int n;
cin >> n;
vector<Point> points(2 * n);
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
points[2 * i] = {x, y, i};
cin >> x >> y;
points[2 * i + 1] = {x, y, i};
}
vector<int> state(n);
for (int &x : state) {
cin >> x;
}
sort(points.begin(), points.end(), [&](Point &a, Point &b) {
int qa = getQuadrant(a);
int qb = getQuadrant(b);
if (qa != qb) return qa < qb;
return det({0, 0, 0}, a, b) > 0;
});
for (int it = 0; it < 2; ++it) {
vector<int> other(n, -1);
Solver solver(2 * n);
solver.add(0, 2 * n, it);
for (int i = 0; i < 2 * n; ++i) {
if (other[points[i].id] != -1) {
if (det({0, 0, 0}, points[other[points[i].id]], points[i]) < 0) {
solver.add(other[points[i].id], i + 1, state[points[i].id] ^ it);
} else {
solver.add(other[points[i].id], i + 1, state[points[i].id]);
}
}
other[points[i].id] = i;
}
if (solver.solve()) {
vector<bool> sol = solver.getSol();
int ans = count(sol.begin(), sol.end(), 1);
cout << ans << endl;
for (int i = 0; i < 2 * n; ++i) {
if (sol[i]) {
cout << getAng(points[i]) << '\n';
//~ cerr << points[i].x << ' ' << points[i].y << ' ' << points[i].id << endl;
}
}
return 0;
}
}
assert(false);
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}