Cod sursa(job #3295511)

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

using namespace std;

struct Point {
    int x, y;
};

bool isOnSegment(Point a, Point b, Point p) {
    // Determinăm dacă punctul p se află pe segmentul [a, b]
    int cross = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
    if (cross != 0) return false;

    int minX = min(a.x, b.x), maxX = max(a.x, b.x);
    int minY = min(a.y, b.y), maxY = max(a.y, b.y);
    return (p.x >= minX && p.x <= maxX && p.y >= minY && p.y <= maxY);
}

bool isInside(const vector<Point>& poly, Point p) {
    int n = poly.size();
    bool inside = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        Point a = poly[j], b = poly[i];

        // verificăm dacă este pe muchie
        if (isOnSegment(a, b, p)) return true;

        // Ray Casting: intersecții cu muchii
        bool intersect = ((a.y > p.y) != (b.y > p.y));
        if (intersect) {
            double x_intersect = (double)(b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x;
            if (p.x < x_intersect)
                inside = !inside;
        }
    }
    return inside;
}

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 cnt = 0;
    for (int i = 0; i < M; ++i) {
        Point p;
        fin >> p.x >> p.y;
        if (isInside(polygon, p))
            ++cnt;
    }

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