Cod sursa(job #2058678)

Utilizator retrogradLucian Bicsi retrograd Data 5 noiembrie 2017 23:43:39
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <bits/stdc++.h>

using namespace std;

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


int main() {
    ifstream cin("poligon.in");
    ofstream cout("poligon.out");

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

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

    for (int i = 0; i < n; ++i) {
        cin >> poly[i].x >> poly[i].y;
        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());

    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);
        }
        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]);

    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]; 
        sort(lines[i].begin(), lines[i].end(), cmp);
    }

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

        // 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;
            }
        }

        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;
            } 
        }
        
        tot += distance(it, lines[idx].end()) % 2;
    }
    cout << tot << endl;

    return 0;
}