Cod sursa(job #3295513)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 6 mai 2025 11:42:12
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <vector>
using namespace std;

struct Point {
    int x, y;
};

bool onSegment(Point a, Point b, Point p) {
    long long cross = 1LL * (b.x - a.x) * (p.y - a.y) - 1LL * (b.y - a.y) * (p.x - a.x);
    if (cross != 0) return false;
    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

bool insidePolygon(const vector<Point>& poly, const Point& p) {
    int cnt = 0;
    int n = poly.size();

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

        if (onSegment(a, b, p))
            return true;

        if (a.y > b.y)
            swap(a, b);

        // Verifică dacă muchia intersectează linia orizontală de la p
        if (p.y > a.y && p.y <= b.y) {
            long long dx = b.x - a.x;
            long long dy = b.y - a.y;
            long long cmp = 1LL * dx * (p.y - a.y) - 1LL * dy * (p.x - a.x);
            if (cmp > 0)
                cnt++;
        }
    }

    return cnt % 2 == 1;
}

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

    int N, M;
    fin >> N >> M;
    vector<Point> poly(N);
    for (int i = 0; i < N; ++i)
        fin >> poly[i].x >> poly[i].y;

    int rez = 0;
    for (int i = 0; i < M; ++i) {
        Point p;
        fin >> p.x >> p.y;
        if (insidePolygon(poly, p))
            ++rez;
    }

    fout << rez << '\n';
    return 0;
}