Cod sursa(job #3300277)

Utilizator Carnu_EmilianCarnu Emilian Carnu_Emilian Data 14 iunie 2025 13:46:33
Problema Poligon Scor 40
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 1.71 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
typedef long long ll;

const int N = 805;

struct Edge {
    int x1, y1, x2, y2;
} v[N];
pair<int, int> f[N];
int n, m, x, y, rasp;

bool valid(int x, int y) {
    bool onBoundary = false;
    int nr = 0;
    for (int i = 1; i <= n; i++) {
        int x1 = v[i].x1, y1 = v[i].y1;
        int x2 = v[i].x2, y2 = v[i].y2;

        ll cross = (ll)(x - x1) * (ll)(y2 - y1) - (ll)(y - y1) * (ll)(x2 - x1);
        if (cross == 0) {
            if (x >= min(x1, x2) && x <= max(x1, x2) && y >= min(y1, y2) && y <= max(y1, y2)) {
                onBoundary = true;
                break;
            }
        }

        if (y1 == y2)
            continue;

        bool above1 = (y1 > y);
        bool above2 = (y2 > y);
        if (above1 == above2)
            continue;

        ll A = (ll)x1 * y2 - (ll)x2 * y1 + (ll)y * (x2 - x1);
        ll denom = y2 - y1;

        if (denom > 0) {
            if (A <= (ll)x * denom)
                nr++;
        } else {
            if (A >= (ll)x * denom)
                nr++;
        }
    }
    if (onBoundary)
        return false;
    return (nr % 2 == 1);
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        fin >> f[i].first >> f[i].second;

    for (int i = 1; i <= n-1; i++) {
        v[i] = { f[i].first, f[i].second, f[i+1].first, f[i+1].second };
    }
    v[n] = { f[n].first, f[n].second, f[1].first, f[1].second };

    rasp = 0;
    while (m--) {
        fin >> x >> y;
        if (valid(x, y))
            rasp++;
    }
    fout << rasp << '\n';
    fin.close();
    fout.close();
    return 0;
}