Cod sursa(job #3357166)

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

using namespace std;

struct Point {
    int x, y; // int este suficient pentru coordonate pana la 60.000 si este mai rapid decat long long in array-uri
};

struct Edge {
    Point a, b;
    int minX, maxX;
};

// Vector de vectori: pentru fiecare coordonata Y de la 0 la 60000, 
// retinem indicii laturilor care trec prin acel Y.
// Folosim un array static sau vector alocat global pentru viteza maxima.
vector<int> bucket[60005];
Edge edges[805];

// Verifica daca P este pe segmentul AB
inline bool isOnSegment(const Point& p, const Point& a, const Point& b, const Edge& edge) {
    if (p.x < edge.minX || p.x > edge.maxX) return false;

    // Cast la long long doar aici unde inmultirea poate depasi int
    long long crossProduct = 1LL * (p.y - a.y) * (b.x - a.x) - 1LL * (p.x - a.x) * (b.y - a.y);
    return crossProduct == 0;
}

int main() {
    // Fortarea la maxim a vitezei 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> v(n);
    for (int i = 0; i < n; ++i) {
        fin >> v[i].x >> v[i].y;
    }

    // Precalculare laturi si distributie in bucket-uri
    for (int i = 0; i < n; ++i) {
        edges[i].a = v[i];
        edges[i].b = v[(i + 1) % n];
        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 minY = min(edges[i].a.y, edges[i].b.y);
        int maxY = max(edges[i].a.y, edges[i].b.y);

        // Adaugam latura in toate bucket-urile Y pe care le acopera
        for (int y = minY; y <= maxY; ++y) {
            bucket[y].push_back(i);
        }
    }

    int validCrimes = 0;
    Point p;

    // Procesare interogari
    for (int i = 0; i < m; ++i) {
        fin >> p.x >> p.y;

        // Daca Y-ul punctului este in afara hartii standard (just in case)
        if (p.y < 0 || p.y > 60000) continue;

        int intersectCount = 0;
        bool onBoundary = false;

        // Verificam DOAR laturile care stim sigur ca ating coordonata p.y
        const vector<int>& activeEdges = bucket[p.y];
        int numActive = activeEdges.size();

        for (int j = 0; j < numActive; ++j) {
            int edgeIdx = activeEdges[j];
            const Edge& edge = edges[edgeIdx];

            // 1. Verificare rapida margine
            if (isOnSegment(p, edge.a, edge.b, edge)) {
                onBoundary = true;
                break;
            }

            // 2. Ray casting strict (conventia jumatatii de interval deschis)
            if ((edge.a.y <= p.y && edge.b.y > p.y) || (edge.b.y <= p.y && edge.a.y > p.y)) {
                long long cross = 1LL * (p.y - edge.a.y) * (edge.b.x - edge.a.x);
                long long deltaY = edge.b.y - edge.a.y;

                if (deltaY > 0 && cross >= 1LL * (p.x - edge.a.x) * deltaY) {
                    intersectCount++;
                } else if (deltaY < 0 && cross <= 1LL * (p.x - edge.a.x) * deltaY) {
                    intersectCount++;
                }
            }
        }

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

    fout << validCrimes << "\n";

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