Cod sursa(job #3319590)

Utilizator unomMirel Costel unom Data 1 noiembrie 2025 22:30:59
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.35 kb
#include <bits/stdc++.h>

using namespace std;

#define int long long

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

struct Edge {
    int x1,y1,x2,y2;
    int ymin, ymax;
    int dx, dy; // x2-x1, y2-y1
};

inline long long det_ll(int x1,int y1,int x2,int y2,int x3,int y3){
    return 1LL*(x2-x1)*(y3-y1) - 1LL*(y2-y1)*(x3-x1);
}

inline bool on_segment(const Edge &e, int px, int py){
    if (det_ll(e.x1,e.y1,e.x2,e.y2,px,py) != 0) return false;
    if (px < min(e.x1,e.x2) || px > max(e.x1,e.x2)) return false;
    if (py < min(e.y1,e.y2) || py > max(e.y1,e.y2)) return false;
    return true;
}

signed main()
{
    int n, m;
    in >> n >> m;

    vector<pair<int,int>> v(n+1);
    for(int i=1;i<=n;i++){
        in >> v[i].first >> v[i].second;
    }

    // build edges
    vector<Edge> edges;
    edges.reserve(n);
    for(int i=1;i<=n;i++){
        int j = (i==n?1:i+1);
        Edge e;
        e.x1 = v[i].first; e.y1 = v[i].second;
        e.x2 = v[j].first; e.y2 = v[j].second;
        e.dx = e.x2 - e.x1;
        e.dy = e.y2 - e.y1;
        e.ymin = min(e.y1, e.y2);
        e.ymax = max(e.y1, e.y2);
        edges.push_back(e);
    }

    // bucketing params
    const int YMAX = 60000;
    const int BLOCK = 128; // ajustabil
    int nblocks = (YMAX / BLOCK) + 3;
    vector<vector<int>> bucket(nblocks);
    vector<vector<int>> horiz(YMAX + 1); // muchii orizontale indexate dupa y

    for(int id = 0; id < (int)edges.size(); ++id){
        Edge &e = edges[id];
        if (e.ymin == e.ymax) {
            // orizontala: store by exact y
            if (e.ymin >= 0 && e.ymin <= YMAX) horiz[e.ymin].push_back(id);
            continue;
        }
        int b1 = e.ymin / BLOCK;
        int b2 = (e.ymax - 1) / BLOCK;
        if (b1 < 0) b1 = 0;
        if (b2 >= nblocks) b2 = nblocks - 1;
        for(int b = b1; b <= b2; ++b) bucket[b].push_back(id);
    }

    int ans = 0;
    for(int qi=0; qi<m; ++qi){
        int px, py;
        in >> px >> py;

        bool onEdge = false;
        int crosses = 0;

        // check horizontals at this y
        if (py >= 0 && py <= YMAX){
            for(int id : horiz[py]){
                const Edge &e = edges[id];
                if (px >= min(e.x1,e.x2) && px <= max(e.x1,e.x2)) { onEdge = true; break; }
            }
            if (onEdge) { ++ans; continue; }
        }

        // check edges from bucket
        int b = py / BLOCK;
        if (b < 0) b = 0;
        if (b >= nblocks) b = nblocks - 1;
        const vector<int> &vec = bucket[b];
        for(int id : vec){
            const Edge &e = edges[id];
            if (!(e.ymin <= py && py < e.ymax)) continue; // not intersecting horizontal line y=py
            // check if on segment (boundary)
            if (on_segment(e, px, py)) { onEdge = true; break; }

            // count crossing: decide if intersection x > px
            // compare (px - x1) * dy  ?  dx * (py - y1)
            long long left = 1LL*(px - e.x1) * e.dy;
            long long right = 1LL*e.dx * (py - e.y1);
            if (e.dy > 0) {
                if (left < right) ++crosses;
            } else { // e.dy < 0
                if (left > right) ++crosses;
            }
        }

        if (onEdge) ++ans;
        else if (crosses & 1) ++ans;
    }

    out << ans;
    return 0;
}