Cod sursa(job #3365895)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 27 septembrie 2026 14:35:21
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3, Ofast, unroll-loops")
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
const pll RANDOM_POINT = {1e6 + 1111, 1e9+17};

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; // trig
    if (x < 0)
        return -1; // non-trig
    return 0;
}
bool on_segment(const pll &a, const pll &b, const pll &p) {
    if (orient(a, b, p) != 0) return false;
    return min(a.first, b.first) <= p.first &&
           p.first <= max(a.first, b.first) &&
           min(a.second, b.second) <= p.second &&
           p.second <= max(a.second, b.second);
}

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);
    }
}
bool check_intesection(const pll &current, const pll &next, const pll &point) {
    int v1 = orient(current, next, point);
    int v2 = orient(current, next, RANDOM_POINT);
    int v3 = orient(point, RANDOM_POINT, current);
    int v4 = orient(point, RANDOM_POINT, next);
    return (v1 != v2 && v3 != v4);
}
int query(const int &n, const pll &point) {
    int intersections = 0;
    for (int i = 0; i < n - 1; i++) {
        pll current = vertices[i];
        pll next = vertices[i + 1];
        if (on_segment(current, next, point)) return 0; // inside
        intersections += check_intesection(current, next, point);
    }
    pll current = vertices[n - 1];
    pll next = vertices[0];
    if (on_segment(current, next, point)) return 0; // inside
    intersections += check_intesection(current, next, point);

    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);
        // if (result == 0)
        //     printf("BOUNDARY\n");
        // else if (result == 1)
        //     printf("INSIDE\n");
        // else
        //     printf("OUTSIDE\n");
        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;
}