Cod sursa(job #2193343)

Utilizator retrogradLucian Bicsi retrograd Data 9 aprilie 2018 19:54:38
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <bits/stdc++.h>

using namespace std;

using T = long long;
using Point = complex<T>;
namespace std {
    bool operator<(const Point& a, const Point& b) {
        if (a.real() == b.real()) 
            return a.imag() < b.imag();
        return a.real() < b.real();
    };
}

T cross(Point a, Point b) { return (conj(a) * b).imag(); }
T det(Point a, Point b, Point c) { return cross(b - a, c - a); }
int sgn(T x) { return (x == 0 ? 0 : x < 0 ? -1 : 1); }

vector<int> PointsInPolygon(vector<Point> P, vector<Point> Q) {
    int n = P.size(), q = Q.size();

    // Step 1: add events to queue
    vector<tuple<Point, int, int, int>> events;
    auto process = [&](int i, int j) {
        events.emplace_back(P[i], 2, i, i);
        if (P[j] < P[i]) swap(i, j);
        if (P[i].real() == P[j].real()) {
            events.emplace_back(P[i], 2, i, j);
        } else {
            events.emplace_back(P[i], 1, i, j);
            events.emplace_back(P[j], 0, i, j);
        }
    };
    for (int j = n - 1, i = 0; i < n; j = i++) 
        process(i, j);
    for (int i = 0; i < q; ++i) 
        events.emplace_back(Q[i], 3, i, -1);
    
    // Step 2: Prepare event state
    sort(events.begin(), events.end()); 
    auto cmp = [](pair<Point, Point> p1, pair<Point, Point> p2) {
        Point a, b, p, q; tie(a, b) = p1; tie(p, q) = p2;
        
        int v1 = sgn(det(a, b, p)) + sgn(det(a, b, q));
        if (v1 != 0) return v1 > 0;
        return sgn(det(p, q, a)) + sgn(det(p, q, b)) > 0;
    };
    set<pair<Point, Point>, decltype(cmp)> s(cmp);
    vector<int> ans(q);
    Point vert{-1, -1}; 
    vert *= (int)(2e9);

    // Step 3: Solve
    for (auto itr : events) {
        int tp, i, j;
        tie(ignore, tp, i, j) = itr;

        if (tp == 0) s.erase({P[i], P[j]});
        if (tp == 1) s.insert({P[i], P[j]});
        if (tp == 2) vert = max(vert, P[j]);
        if (tp == 3) {
            auto q = Q[i];
            auto it = s.lower_bound({q, q + 1LL});
            int dist = distance(s.begin(), it);
            ans[i] = (dist % 2 ? -1 : 1);
            
            if ((it != s.end() && det(it->first, it->second, q) == 0)
             || (vert.real() == q.real() && vert.imag() >= q.imag()))
                ans[i] = 0;
        }
    }
    return ans;
}

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

    int n, q; cin >> n >> q;
    vector<Point> P;
    for (int i = 0; i < n; ++i) {
        long long x, y; cin >> x >> y;
        P.emplace_back(x, y);
    }
    vector<Point> Q;
    for (int i = 0; i < q; ++i) {
        long long x, y; cin >> x >> y;
        Q.emplace_back(x, y);
    }

    int cnt = 0;
    auto ans = PointsInPolygon(P, Q);
    for (auto x : ans) 
        cnt += (x >= 0);
    cout << cnt << endl;

    return 0;
}