Cod sursa(job #3359210)

Utilizator rares89_Dumitriu Rares rares89_ Data 26 iunie 2026 03:48:09
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.56 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXC = 60000;

struct Point {
    int x, y;
};

struct Edge {
    int x1, y1, x2, y2;
};

int n, m, ans, y_now;
vector<Point> p, q;
vector<Edge> e;
vector<int> add_edge[MAXC + 5], rem_edge[MAXC + 5], query[MAXC + 5];
vector<pair<int, int> > oriz[MAXC + 5];
vector<int> active;
set<pair<int, int> > vertex;

long long num(int id) {
    Edge a = e[id];

    return 1LL * a.x1 * (a.y2 - a.y1) + 1LL * (y_now - a.y1) * (a.x2 - a.x1);
}

long long den(int id) {
    return e[id].y2 - e[id].y1;
}

bool cmp_edge(int a, int b) {
    long long x = num(a) * den(b);
    long long y = num(b) * den(a);

    if(x != y) return x < y;
    return a < b;
}

bool edge_less_x(int id, int x) {
    return num(id) < 1LL * x * den(id);
}

bool edge_le_x(int id, int x) {
    return num(id) <= 1LL * x * den(id);
}

bool edge_eq_x(int id, int x) {
    return num(id) == 1LL * x * den(id);
}

void erase_edge(int id) {
    for(int i = 0; i < (int)active.size(); i++) {
        if(active[i] == id) {
            active.erase(active.begin() + i);
            return;
        }
    }
}

void insert_edge(int id) {
    int st = 0, dr = active.size();

    while(st < dr) {
        int mid = (st + dr) / 2;

        if(cmp_edge(active[mid], id)) st = mid + 1;
        else dr = mid;
    }

    active.insert(active.begin() + st, id);
}

bool on_horizontal(int x, int y) {
    vector<pair<int, int> > &v = oriz[y];

    int st = 0, dr = (int)v.size() - 1;

    while(st <= dr) {
        int mid = (st + dr) / 2;

        if(v[mid].second < x) {
            st = mid + 1;
        } else if(v[mid].first > x) {
            dr = mid - 1;
        } else {
            return 1;
        }
    }

    return 0;
}

bool on_slanted(int x) {
    int st = 0, dr = active.size();

    while(st < dr) {
        int mid = (st + dr) / 2;

        if(edge_less_x(active[mid], x)) st = mid + 1;
        else dr = mid;
    }

    return st < (int)active.size() && edge_eq_x(active[st], x);
}

int first_greater(int x) {
    int st = 0, dr = active.size();

    while(st < dr) {
        int mid = (st + dr) / 2;

        if(edge_le_x(active[mid], x)) st = mid + 1;
        else dr = mid;
    }

    return st;
}

int main() {
    fin >> n >> m;

    p.resize(n);
    q.resize(m);

    for(int i = 0; i < n; i++) {
        fin >> p[i].x >> p[i].y;
        vertex.insert({p[i].x, p[i].y});
    }

    for(int i = 0; i < n; i++) {
        Point a = p[i];
        Point b = p[(i + 1) % n];

        if(a.y == b.y) {
            int x1 = min(a.x, b.x);
            int x2 = max(a.x, b.x);

            oriz[a.y].push_back({x1, x2});
        } else {
            if(a.y > b.y) {
                swap(a, b);
            }

            int id = e.size();

            e.push_back({a.x, a.y, b.x, b.y});

            add_edge[a.y].push_back(id);
            rem_edge[b.y].push_back(id);
        }
    }

    for(int i = 0; i <= MAXC; i++) {
        sort(oriz[i].begin(), oriz[i].end());

        vector<pair<int, int> > aux;

        for(int j = 0; j < (int)oriz[i].size(); j++) {
            if(aux.empty() || oriz[i][j].first > aux.back().second) {
                aux.push_back(oriz[i][j]);
            } else {
                aux.back().second = max(aux.back().second, oriz[i][j].second);
            }
        }

        oriz[i] = aux;
    }

    for(int i = 0; i < m; i++) {
        fin >> q[i].x >> q[i].y;
        query[q[i].y].push_back(i);
    }

    for(y_now = 0; y_now <= MAXC; y_now++) {
        for(int i = 0; i < (int)rem_edge[y_now].size(); i++) {
            erase_edge(rem_edge[y_now][i]);
        }

        for(int i = 0; i < (int)add_edge[y_now].size(); i++) {
            insert_edge(add_edge[y_now][i]);
        }

        for(int i = 0; i < (int)query[y_now].size(); i++) {
            int id = query[y_now][i];
            int x = q[id].x;

            if(vertex.count({x, y_now})) {
                ans++;
                continue;
            }

            if(on_horizontal(x, y_now)) {
                ans++;
                continue;
            }

            if(on_slanted(x)) {
                ans++;
                continue;
            }

            int poz = first_greater(x);
            int cnt = (int)active.size() - poz;

            if(cnt % 2 == 1) {
                ans++;
            }
        }
    }

    fout << ans << "\n";

    return 0;
}