Pagini recente » Cod sursa (job #2077573) | Cod sursa (job #2901974) | Cod sursa (job #2796500) | Cod sursa (job #1910618) | Cod sursa (job #1820566)
#include <bits/stdc++.h>
using namespace std;
typedef long double f80;
const int SPQR = 520; // Ave Imperator, morituri te salutant!
const f80 EPS = 1e-7L,
PI = 3.14159265358979323846264338327950288419716939937510582L; // A good PIN...
struct PTX {
f80 x, y; };
ifstream fi("laser.in");
ofstream fo("laser.out");
int n, m;
vector<PTX> seg;
vector<f80> ray, tgs, sol;
vector<int> point;
bitset<SPQR*2> gauss[SPQR];
inline f80 atan3(const f80 &x, const f80 &y) {
f80 ang = atan2(x, y);
if (ang < 0.0)
return ang + 2 * PI;
else
return ang; }
inline f80 get_ang(const PTX &seg) {
return min(seg.y - seg.x, 2 * PI - seg.y + seg.x); }
inline bool in(const f80 &ang, const PTX &seg) {
if ((seg.y - seg.x) < PI)
return ((seg.x - EPS) < ang) && (ang < (seg.y + EPS));
else
return (seg.y < (ang + EPS)) || ((ang - EPS) < seg.x); }
void get_gauss(void) {
int i, j, k;
i = j = 0;
while (i < n && j < m) {
if (!gauss[i][j]) {
for (k = i; k < n && !gauss[k][j]; ++k);
if (k == n) {
++j;
continue; }
swap(gauss[i], gauss[k]); }
if (gauss[i][j])
for (k = 0; k < n; ++k) if (i != k && gauss[k][j])
gauss[k]^= gauss[i];
point[i] = j;
++ i;
++ j; } /* csz... ms Ade... */ }
int main(void) {
f80 x, y;
int tmp;
fi >> n;
m = n * 2;
seg.resize(n);
point.resize(n);
for (auto &i: seg) {
fi >> x >> y; i.x = atan3(x, y);
fi >> x >> y; i.y = atan3(x, y);
if (i.x > i.y)
swap(i.x, i.y);
tgs.push_back(i.x);
tgs.push_back(i.y); }
sort(tgs.begin(), tgs.end());
for (int i = 1; i < tgs.size(); ++i)
ray.push_back((tgs[i - 1] + tgs[i]) / 2.0);
ray.push_back((tgs.front() + tgs.back() / 2.0));
if (ray.back() > 2 * PI + EPS) {
ray.insert(ray.begin(), ray.back() - 2 * PI);
ray.pop_back(); }
for (int i = 0; i < n; ++i) {
fi >> tmp;
gauss[i] = 0;
gauss[i][m] = tmp; }
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
gauss[i][j] = in(ray[j], seg[i]);
get_gauss();
for (int i = 0; i < n; ++i)
if (gauss[i][m])
sol.push_back((point[i] % 2) ? seg[point[i / 2]].y : seg[point[i / 2]].x);
fo << setprecision(6) << fixed;
fo << sol.size() << '\n';
for (const auto &i: sol)
fo << (i * 180.0L / PI) << '\n';
return 0; }