Cod sursa(job #3357165)

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

using namespace std;

struct Point {
    long long x, y;
};

// Structura pentru a retine o latura si bounding box-ul ei pe Y
struct Edge {
    Point a, b;
    long long minY, maxY;
    long long minX, maxX;
};

// Verifica rapid daca P poate fi pe segmentul AB
inline bool isOnSegment(const Point& p, const Point& a, const Point& b, const Edge& edge) {
    // Daca P e in afara cutiei delimitate de segment, nu e pe segment
    if (p.x < edge.minX || p.x > edge.maxX || p.y < edge.minY || p.y > edge.maxY) {
        return false;
    }
    // Verificare coliniaritate
    long long crossProduct = (p.y - a.y) * (b.x - a.x) - (p.x - a.x) * (b.y - a.y);
    return crossProduct == 0;
}

int main() {
    // Optimizare maxima pentru I/O standard
    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> v(n);
    for (int i = 0; i < n; ++i) {
        fin >> v[i].x >> v[i].y;
    }

    // Pre-calculam laturile si limitele lor pentru a nu repeta operatiile in bucla mare
    vector<Edge> edges(n);
    for (int i = 0; i < n; ++i) {
        edges[i].a = v[i];
        edges[i].b = v[(i + 1) % n];
        edges[i].minY = min(edges[i].a.y, edges[i].b.y);
        edges[i].maxY = max(edges[i].a.y, edges[i].b.y);
        edges[i].minX = min(edges[i].a.x, edges[i].b.x);
        edges[i].maxX = max(edges[i].a.x, edges[i].b.x);
    }

    int validCrimes = 0;
    Point p;

    // Procesam cele M puncte
    for (int i = 0; i < m; ++i) {
        fin >> p.x >> p.y;

        int intersectCount = 0;
        bool onBoundary = false;

        for (int j = 0; j < n; ++j) {
            // 1. Quick check: daca schita Y a laturii nu intersecteaza nivelul p.y, trecem mai departe
            if (p.y < edges[j].minY || p.y > edges[j].maxY) {
                continue;
            }

            // 2. Verificam daca e pe margine
            if (isOnSegment(p, edges[j].a, edges[j].b, edges[j])) {
                onBoundary = true;
                break; // Daca e pe margine, stim sigur ca e valid, nu mai numaram
            }

            // 3. Ray casting strict pentru laturile ramase
            // Conditia stricta de intersectie (folosind conventia jumatatii deschise de interval)
            if ((edges[j].a.y <= p.y && edges[j].b.y > p.y) || (edges[j].b.y <= p.y && edges[j].a.y > p.y)) {
                long long cross = (p.y - edges[j].a.y) * (edges[j].b.x - edges[j].a.x);
                long long deltaY = edges[j].b.y - edges[j].a.y;

                if (deltaY > 0 && cross >= (p.x - edges[j].a.x) * deltaY) {
                    intersectCount++;
                } else if (deltaY < 0 && cross <= (p.x - edges[j].a.x) * deltaY) {
                    intersectCount++;
                }
            }
        }

        if (onBoundary || (intersectCount % 2 != 0)) {
            validCrimes++;
        }
    }

    fout << validCrimes << "\n";

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