Cod sursa(job #3366688)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 3 octombrie 2026 15:48:14
Problema Poligon Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

ll get_determinator(const pll &a, const pll &b) {
    return (a.first * b.second - a.second * b.first);
}
ll get_orient_value(const pll &a, const pll &b, const pll &c) {
    return get_determinator(a, b) + get_determinator(b, c) + get_determinator(c, a);
}
int orient(const pll &a, const pll &b, const pll &c) {
    ll x = get_orient_value(a, b, c);
    if (x > 0)
        return 1;
    if (x < 0)
        return -1;
    return 0;
}

vector<pll> vertices;
void read_input(int &n, int &m) {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        pll x;
        scanf("%lld %lld", &x.first, &x.second);
        vertices.push_back(x);
    }
}
int query(const int &n, const pll &p) {
    int intersections = 0;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        const pll &a = vertices[j];
        const pll &b = vertices[i];
        if (p.second < min(a.second, b.second) || p.second > max(a.second, b.second))
            continue;

        int o = orient(a, b, p);
        if (o == 0 && min(a.first, b.first) <= p.first && p.first <= max(a.first, b.first))
            return 0;

        if ((a.second > p.second) != (b.second > p.second)) {
            int s = (a.second < b.second) ? o : -o;
            if (s > 0) intersections++;
        }
    }
    return (intersections % 2 == 0) ? -1 : 1;
}
void solve_queries(const int &n, const int &m) {
    int x = 0;
    for (int _ = 1; _ <= m; _++) {
        pll point; scanf("%lld %lld", &point.first, &point.second);
        int result = query(n, point);
        x += (result == 1 || result == 0);
    }
    printf("%d\n", x);
}
int main() {
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);
    int n, m;
    read_input(n, m);
    solve_queries(n, m);

    return 0;
}