Cod sursa(job #3359209)

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

using namespace std;

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

const int MAXC = 60000;
const double EPS = 1e-9;

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;

double get_x(int id) {
    Edge a = e[id];

    return a.x1 + 1.0 * (y_now - a.y1) * (a.x2 - a.x1) / (a.y2 - a.y1);
}

bool cmp_edge(int a, int b) {
    double x1 = get_x(a);
    double x2 = get_x(b);

    if(abs(x1 - x2) > EPS) return x1 < x2;
    return a < b;
}

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(get_x(active[mid]) < x - EPS) st = mid + 1;
        else dr = mid;
    }

    if(st < (int)active.size() && abs(get_x(active[st]) - x) <= EPS) return 1;
    return 0;
}

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

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

        if(get_x(active[mid]) <= x + EPS) 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++) {
        if(oriz[i].empty()) continue;

        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 + 1) {
                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 != 0) {
                ans++;
            }
        }
    }

    fout << ans << "\n";

    return 0;
}