Cod sursa(job #1968590)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 17 aprilie 2017 19:23:01
Problema Poligon Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("poligon.in");
ofstream fo("poligon.out");

using f64 = long double;

const f64 C = cos(1.3241), S = sin(1.3241), EPS = 1e-7;
const int N = 805;

struct Ptx {
    f64 x, y;

    Ptx rot() {
        f64 nx = x * C + y * S, ny = y * C - x * S;
        x = nx, y = ny;
        return *this; }

    inline bool operator < (const Ptx &arg) const {
        return x < arg.x; }

    inline bool operator > (const Ptx &arg) const {
        return x > arg.x; }

    inline bool operator == (const Ptx &arg) const {
        return abs(x - arg.x) < EPS && abs(y - arg.y) < EPS; } };

struct Seg {
    f64 a, b;

    inline Seg() { }
    inline Seg(const Ptx &v, const Ptx &w) {
        a = (v.y - w.y) / (v.x - w.x);
        b = v.y - a * v.x; }

    inline f64 operator [] (const f64 &x) const {
        return x * a + b; }
    inline bool operator < (const Ptx &arg) const {
        return arg.y > arg.x * a + b; }
    inline bool operator > (const Ptx &arg) const {
        return arg.y < arg.x * a + b; }
    inline bool operator == (const Ptx &arg) const {
        return abs(arg.y - (arg.x * a + b)) < EPS; } };

vector<Seg> str[N];
vector<Ptx> pts;
vector<int> srt;
int n, m;

void get_strips() {
    Ptx x, y;

    srt.resize(n);
    iota(begin(srt), end(srt), 0);
    sort(begin(srt), end(srt), [pts](int a, int b) {
        return pts[a] < pts[b]; });

    for (int i = 1; i < n; ++i) {
        x = pts[srt[i - 1]];
        y = pts[srt[i]];
        for (int j = 0; j < n; ++j)
            if (min(pts[j], pts[(j + 1) % n]).x - EPS < x.x && y.x < max(pts[j], pts[(j + 1) % n]).x + EPS)
                str[i].emplace_back(pts[j], pts[(j + 1) % n]);

        sort(begin(str[i]), end(str[i]), [x = pts[srt[i - 1]].x, px = pts[srt[i]].x](const Seg &a, const Seg &b) {
            return (abs(a[x] - b[x]) < EPS) ? (a[px] < b[px]) : (a[x] < b[x]); }); } }

bool in(Ptx arg) {
    int strip = -1, line = -1;

    if (arg < pts[srt.front()])
        return false;
    if (arg > pts[srt.back()])
        return false;

    for (int msk = 1 << 10; msk; msk>>= 1)
        if (strip + msk < n && pts[srt[strip + msk]].x < arg.x)
            strip+= msk;
    ++strip;

    for (int msk = 1 << 10; msk; msk>>= 1)
        if (line + msk < str[strip].size() && str[strip][line + msk] < arg)
            line+= msk;

    if (line % 2 == 0)
        return true;

    if (line >= 0 && str[strip][line] == arg)
        return true;
    if (line + 1 < str[strip].size() && str[strip][line + 1] == arg)
        return true;

    return false; }

int main() {
    int ant = 0;
    Ptx p;

    fi >> n >> m;

    pts.resize(n);
    for (auto &i: pts) {
        fi >> i.x >> i.y;
        i.x+= 1.0, i.y+= 1.0;
        i.rot(); }

    get_strips();

    while (m--) {
        fi >> p.x >> p.y;
        p.x+= 1.0, p.y+= 1.0;
        ant+= in(p.rot()) ? 1 : 0; }

    fo << ant << '\n';
    cerr << ant << '\n';

    return 0; }