Cod sursa(job #3295512)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 6 mai 2025 11:38:04
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <vector>

using namespace std;

struct Point {
    int x, y;
};

bool isOnSegment(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 isInsidePolygon(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 (isOnSegment(a, b, p))
            return true;

        // testăm intersecția razei orizontale pornind din p cu segmentul [a,b]
        if (a.y > b.y)
            swap(a, b);

        if (p.y > a.y && p.y <= b.y) {
            long long orient = 1LL * (b.x - a.x) * (p.y - a.y) - 1LL * (b.y - a.y) * (p.x - a.x);
            if (orient > 0)
                ++cnt;
        }
    }

    return cnt % 2 == 1;
}

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

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

    int count = 0;
    for (int i = 0; i < M; ++i) {
        Point p;
        fin >> p.x >> p.y;
        if (isInsidePolygon(polygon, p))
            ++count;
    }

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