Cod sursa(job #3357164)

Utilizator parus_majorParus Major parus_major Data 6 iunie 2026 18:16:16
Problema Poligon Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
    long long x, y;
};

// Verifica daca punctul P se afla pe segmentul AB
bool isOnSegment(Point p, Point a, Point b) {
    // Verificare coliniaritate folosind produsul vectorial (cross product)
    long long crossProduct = (p.y - a.y) * (b.x - a.x) - (p.x - a.x) * (b.y - a.y);
    if (crossProduct != 0) {
        return false;
    }
    // Verificare daca P este in interiorul cutiei delimitate de A si B
    return p.x >= min(a.x, b.x) && p.x <= max(a.x, b.x) &&
        p.y >= min(a.y, b.y) && p.y <= max(a.y, b.y);
}

// Verifica daca punctul este inside sau pe marginea poligonului
bool isInsideOrOnBoundary(Point p, const vector<Point>& polygon, int n) {
    int intersectCount = 0;

    for (int i = 0; i < n; ++i) {
        Point a = polygon[i];
        Point b = polygon[(i + 1) % n]; // Urmatorul varf (inchide poligonul)

        // Daca punctul e pe margine, returnam direct true
        if (isOnSegment(p, a, b)) {
            return true;
        }

        // Ray casting: tragem o raza spre dreapta de la P
        // Verificam daca segmentul AB intersecteaza linia orizontala y = p.y
        if ((a.y <= p.y && b.y > p.y) || (b.y <= p.y && a.y > p.y)) {
            // Calculam coordonata X a intersectiei segmentului cu dreapta y = p.y
            // Folosim inmultire in loc de impartire pentru a evita float/double
            // x_intersect = a.x + (p.y - a.y) * (b.x - a.x) / (b.y - a.y)
            long long cross = (p.y - a.y) * (b.x - a.x);
            long long deltaY = b.y - a.y;

            // Verificam daca punctul de intersectie este la dreapta lui p.x
            // Trebuie sa fim atenti la semnul lui deltaY
            if (deltaY > 0 && cross >= (p.x - a.x) * deltaY) {
                intersectCount++;
            } else if (deltaY < 0 && cross <= (p.x - a.x) * deltaY) {
                intersectCount++;
            }
        }
    }

    // Daca numarul de intersectii este impar, punctul este inauntru
    return (intersectCount % 2 != 0);
}

int main() {
    // Optimizare pentru operatiile de I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    int n, m;
    if (!(fin >> n >> m)) return 0;

    vector<Point> polygon(n);
    for (int i = 0; i < n; ++i) {
        fin >> polygon[i].x >> polygon[i].y;
    }

    int validCrimes = 0;
    for (int i = 0; i < m; ++i) {
        Point p;
        fin >> p.x >> p.y;
        if (isInsideOrOnBoundary(p, polygon, n)) {
            validCrimes++;
        }
    }

    fout << validCrimes << "\n";

    fin.close();
    fout.close();
    return 0;
}