Cod sursa(job #1820568)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 1 decembrie 2016 21:32:05
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#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(ray[point[i]]);

    fo << setprecision(6) << fixed;
    fo << sol.size() << '\n';
    for (const auto &i: sol)
        fo << (i * 180.0L / PI) << '\n';

    return 0; }