Cod sursa(job #1820596)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 1 decembrie 2016 21:58:51
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
// atan2 is f*cking evil
#include <bits/stdc++.h>
using namespace std;
typedef double f80;

const int SPQR = 520; // Ave Imperator, morituri te salutant!
const f80 EPS = 1e-7,
           PI = 3.14159265358979323846264338327950288419716939937510582; // 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(y, x); // O.o
    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());
    tgs.push_back(tgs.front() + 2.0 * PI);

    for (int i = 0; i < m; ++i)
        ray.push_back((tgs[i] + tgs[i + 1]) / 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 / PI) << '\n';

    return 0; }