Cod sursa(job #2058712)

Utilizator retrogradLucian Bicsi retrograd Data 6 noiembrie 2017 00:49:11
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <bits/stdc++.h>

using namespace std;

struct Point {
    int x, y;
    complex<int> toc() { return complex<int>(x, y); }
};

Point Read() {
    Point ret;
    cin >> ret.x >> ret.y;
    ret.x *= 2; ret.y *= 2;
    return ret;
}

int main() {
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);
    ios_base::sync_with_stdio(false);

    int n, m; cin >> n >> m;

    vector<Point> poly(n);
    vector<int> xs;

    for (int i = 0; i < n; ++i) {
        poly[i] = Read();
        xs.push_back(poly[i].x);
    }

    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    vector<vector<pair<Point, Point>>> lines(xs.size());
    vector<map<int, int>> verts(xs.size());
    vector<set<int>> points(xs.size());

    auto ins_segm = [&](Point a, Point b) {
        if (a.x > b.x) swap(a, b);
        if (a.x == b.x) {
            int idx = lower_bound(xs.begin(), xs.end(), a.x) - xs.begin();
            verts[idx][min(a.y, b.y)] = max(a.y, b.y);
        } else {
            for (int i = 0; i < (int)xs.size(); ++i) {
                if (xs[i] >= a.x && xs[i] < b.x)
                    lines[i].emplace_back(a, b);
            }
        }
    };

    for (int i = 0, j = n - 1; i < n; j = i++) {
        ins_segm(poly[j], poly[i]);
        int idx = lower_bound(xs.begin(), xs.end(), poly[i].x) - xs.begin();
        points[idx].insert(poly[i].y);
    }

    auto eval = [](Point a, Point b, int x) {
        // (x - a.x) / (b.x - a.x) = (y - a.y) / (b.y - a.y)
        long long up = 1LL * a.y * (b.x - a.x)
            + 1LL * (x - a.x) * (b.y - a.y);
        long long dw = b.x - a.x;
        return make_pair(up, dw);
    };

    int cmp_x;
    auto cmp = [&](pair<Point, Point> a, pair<Point, Point> b) {
        auto r1 = eval(a.first, a.second, cmp_x),
             r2 = eval(b.first, b.second, cmp_x);
        return r1.first * r2.second < r1.second * r2.first;
    };
    
    for (int i = 0; i < (int)lines.size(); ++i) {
        cmp_x = xs[i] + 1; 
        sort(lines[i].begin(), lines[i].end(), cmp);
    }

    int tot = 0;
    for (int i = 0; i < m; ++i) {
        Point p = Read();
 
        int idx = upper_bound(xs.begin(), xs.end(), p.x)
            - xs.begin() - 1;

        if (idx < 0) continue;
        
        // Check against verts
        if (xs[idx] == p.x) {
            auto it = verts[idx].upper_bound(p.y);
            if (it != verts[idx].begin() && prev(it)->second >= p.y) {
                // On polygon
                tot += 1;
                continue;
            }

            if (points[idx].count(p.y)) {
                // Vertex
                tot += 1;
                continue;
            }
        }

        cmp_x = p.x;
        auto it = lower_bound(lines[idx].begin(), lines[idx].end(), 
                make_pair(Point{p.x, p.y}, Point{p.x + 1, p.y}), cmp);
        
        if (it != lines[idx].end()) {
            auto yn = eval(it->first, it->second, p.x);
            if (yn.first == yn.second * p.y) {
                // On polygon
                tot += 1;
                continue;
            } 
        }
        
        
        bool in = distance(it, lines[idx].begin()) % 2;
        tot += in;
    }
    cout << tot << endl;

    return 0;
}