Cod sursa(job #3359211)

Utilizator rares89_Dumitriu Rares rares89_ Data 26 iunie 2026 03:49:41
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.63 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;
};

int n, m, ans;
vector<Point> p, q;
vector<int> query[MAXC + 5];
vector<int> ys;
bool used[MAXC + 5];
vector<int> sol;

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

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

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

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

        query[q[i].y].push_back(i);

        if(!used[q[i].y]) {
            used[q[i].y] = 1;
            ys.push_back(q[i].y);
        }
    }

    for(int t = 0; t < (int)ys.size(); t++) {
        int y = ys[t];

        vector<int> ids = query[y];
        vector<double> inter;
        vector<pair<int, int> > oriz;

        sort(ids.begin(), ids.end(), [&](int a, int b) {
            return q[a].x < q[b].x;
        });

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

            if(a.y == b.y) {
                if(a.y == y) {
                    oriz.push_back({min(a.x, b.x), max(a.x, b.x)});
                }

                continue;
            }

            Point jos = a;
            Point sus = b;

            if(jos.y > sus.y) {
                swap(jos, sus);
            }

            if(jos.y <= y && y <= sus.y) {
                long long den = sus.y - jos.y;
                long long nr = 1LL * jos.x * den + 1LL * (y - jos.y) * (sus.x - jos.x);

                if(nr % den == 0) {
                    int x = nr / den;

                    int poz = lower_bound(ids.begin(), ids.end(), x, [&](int id, int val) {
                        return q[id].x < val;
                    }) - ids.begin();

                    while(poz < (int)ids.size() && q[ids[poz]].x == x) {
                        sol[ids[poz]] = 1;
                        poz++;
                    }
                }
            }

            if((a.y > y) != (b.y > y)) {
                double x = a.x + 1.0 * (y - a.y) * (b.x - a.x) / (b.y - a.y);
                inter.push_back(x);
            }
        }

        sort(oriz.begin(), oriz.end());

        for(int i = 0, j = 0; i < (int)oriz.size(); i++) {
            while(j < (int)ids.size() && q[ids[j]].x < oriz[i].first) {
                j++;
            }

            while(j < (int)ids.size() && q[ids[j]].x <= oriz[i].second) {
                sol[ids[j]] = 1;
                j++;
            }
        }

        if((int)ids.size() <= 20) {
            for(int i = 0; i < (int)ids.size(); i++) {
                int id = ids[i];

                if(sol[id]) continue;

                int cnt = 0;

                for(int j = 0; j < (int)inter.size(); j++) {
                    if(inter[j] > q[id].x) {
                        cnt++;
                    }
                }

                if(cnt % 2 == 1) {
                    sol[id] = 1;
                }
            }
        } else {
            sort(inter.begin(), inter.end());

            for(int i = 0; i < (int)ids.size(); i++) {
                int id = ids[i];

                if(sol[id]) continue;

                int poz = upper_bound(inter.begin(), inter.end(), q[id].x) - inter.begin();
                int cnt = (int)inter.size() - poz;

                if(cnt % 2 == 1) {
                    sol[id] = 1;
                }
            }
        }
    }

    for(int i = 0; i < m; i++) {
        ans += sol[i];
    }

    fout << ans << "\n";

    return 0;
}