Pagini recente » Cod sursa (job #1154975) | Cod sursa (job #2124610) | Cod sursa (job #986702) | Cod sursa (job #2613827) | Cod sursa (job #2690471)
#include <bits/stdc++.h>
using namespace std;
const double PI = 4.0 * atan(1.0);
struct Angle {
int x = 0, y = 0;
int half() const {
assert(x || y);
return y < 0 || (y == 0 && x < 0);
}
};
bool operator<(const Angle& a, const Angle& b) {
return make_tuple(a.half(), a.y * b.x)
< make_tuple(b.half(), b.y * a.x);
}
bool operator==(Angle a, Angle b) {
return a.half() == b.half() && a.x * b.y == a.y * b.x;
}
pair<Angle, Angle> SegmentAngles(Angle a, Angle b) {
if (b < a) swap(a, b);
if (a.half() || b < Angle{-a.x, -a.y})
swap(a, b);
return {a, b};
}
struct DSU {
vector<int> link;
DSU(int n) : link(n, -1) {}
int Find(int x) {
if (link[x] == -1) return x;
return link[x] = Find(link[x]);
}
bool Union(int a, int b) {
a = Find(a); b = Find(b);
if (a == b) return false;
if (a < b) swap(a, b);
link[a] = b; return true;
}
};
int main() {
ifstream cin("laser.in");
ofstream cout("laser.out");
int n; cin >> n;
vector<Angle> angs(2 * n);
vector<pair<Angle, Angle>> segs(n);
for (int i = 0; i < n; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
Angle a1{x1, y1};
Angle a2{x2, y2};
segs[i] = SegmentAngles(a1, a2);
angs[2 * i + 0] = a1;
angs[2 * i + 1] = a2;
}
sort(angs.begin(), angs.end());
angs.erase(unique(angs.begin(), angs.end()), angs.end());
auto get = [&](Angle a) {
auto it = lower_bound(angs.begin(), angs.end(), a);
assert(it != angs.end() && *it == a);
return it - angs.begin();
};
vector<int> l(n), r(n), v(n);
for (int i = 0; i < n; ++i) {
l[i] = get(segs[i].first);
r[i] = get(segs[i].second);
}
for (int i = 0; i < n; ++i)
cin >> v[i];
int m = angs.size();
angs.push_back(angs[0]);
for (int s = 0; s < 2; ++s) {
DSU D(2 * m + 2);
bool fail = false;
auto add = [&](int a, int b, int c) {
D.Union(2 * a, (2 * b) ^ c);
D.Union(2 * a + 1, (2 * b) ^ c ^ 1);
fail |= (D.Find(2 * a) == D.Find(2 * a + 1));
};
add(0, m, s);
for (int i = 0; i < n; ++i)
add(l[i], r[i], v[i] ^ (l[i] <= r[i] ? 0 : s));
if (fail) continue;
vector<double> ans;
vector<bool> sol(m + 1, 0);
for (int i = 1; i <= m; ++i) {
int rt = D.Find(2 * i);
if (rt != 2 * i)
sol[i] = (sol[rt / 2] ^ (rt % 2));
if (sol[i - 1] == sol[i]) continue;
double a1 = atan2(angs[i - 1].y, angs[i - 1].x),
a2 = atan2(angs[i].y, angs[i].x);
double da = a2 - a1;
while (da > 2 * PI) da -= 2 * PI;
while (da < 0) da += 2 * PI;
double ang = a1 + da / 2;
ang = ang * 180 / PI;
while (ang < 0) ang += 360;
while (ang > 360) ang -= 360;
ans.push_back(ang);
}
cout << ans.size() << '\n';
cout << fixed << setprecision(6);
for (auto x : ans) cout << x << "\n";
return 0;
}
assert(false);
}