Cod sursa(job #3319588)

Utilizator unomMirel Costel unom Data 1 noiembrie 2025 22:28:44
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.97 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

inline ll detll(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){
    // check collinear + bounding box
    if (detll(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;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // folosim scanf/printf pentru viteza I/O
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    vector<int> vx(n+1), vy(n+1);
    for(int i=1;i<=n;i++) scanf("%d %d", &vx[i], &vy[i]);
    // close polygon
    vx.push_back(vx[1]); vy.push_back(vy[1]);

    // parametri bucketing
    const int BLOCK = 128; // dimensiune bloc (ajustabil) -> 60000/128 ≈ 469 blocuri
    const int YMAX = 60000;
    int nblocks = (YMAX / BLOCK) + 2;
    vector<vector<int>> bucket(nblocks);

    vector<Edge> edges;
    edges.reserve(n);
    for(int i=1;i<=n;i++){
        Edge e;
        e.x1 = vx[i];
        e.y1 = vy[i];
        e.x2 = (i==n ? vx[1] : vx[i+1]);
        e.y2 = (i==n ? vy[1] : vy[i+1]);
        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);
        int id = edges.size();
        edges.push_back(e);
        // daca muchia e orizontala, o ignoram pentru ray-crossing (dar o vom verifica la on-segment)
        if (e.ymin == e.ymax) continue;
        int b1 = e.ymin / BLOCK;
        int b2 = (e.ymax - 1) / BLOCK; // half-open [ymin, ymax)
        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;
        scanf("%d %d", &px, &py);
        int b = py / BLOCK;
        if (b < 0) b = 0;
        if (b >= nblocks) b = nblocks-1;

        bool onEdge = false;
        int crosses = 0;

        // iterate doar muchiile din bucket-ul blocului y
        const vector<int> &vec = bucket[b];
        for(int idx : vec){
            const Edge &e = edges[idx];
            // daca punctul y nu e in intervalul [ymin, ymax) -> nu intersecteaza
            if (!(e.ymin <= py && py < e.ymax)) continue;

            // verificare pe segment (inclusiv muchii orizontale care nu sunt in bucket)
            // dar on_segment trebuie verificat și pentru muchiile orizontale (pe care nu le-am pus in bucket)
            if (on_segment(e, px, py)) { onEdge = true; break; }

            // acum calculam daca intersectia cu linia y=py se afla la x > px
            // evitam impartirea: comparam (px - x1) * dy  cu dx * (py - y1)
            ll left = 1LL*(px - e.x1) * e.dy;
            ll right = 1LL*e.dx * (py - e.y1);
            if (e.dy > 0) {
                if (left < right) crosses++;
            } else { // e.dy < 0
                if (left > right) crosses++;
            }
        }

        // trebuie in plus sa verificam daca punctul sta exact pe vreo muchie orizontala,
        // deoarece pentru muchiile orizontale nu am pus in bucket. Verificarea completa de
        // on-segment pe toate muchiile ar fi scumpa; dar putem verifica vârfurile vecine
        // (N mici = 800): verificare rapida a tuturor muchiilor doar pentru cazurile rare:
        if (!onEdge){
            // verificare rapida pe toate muchiile orizontale sau cele care nu erau in bucket
            // (aceasta verificare e rară în mod normal; N=800 e acceptabil)
            for(const Edge &e : edges){
                if (on_segment(e, px, py)){ onEdge = true; break; }
            }
        }

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

    printf("%d", ans);
    return 0;
}