Cod sursa(job #3319586)

Utilizator unomMirel Costel unom Data 1 noiembrie 2025 22:27:01
Problema Poligon Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <bits/stdc++.h>
using namespace std;

int n, m;
int vx[805], vy[805];

// returneaza determinatul (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)
inline long long det_ll(int x1, int y1, int x2, int y2, int x3, int y3) {
    return 1LL * (x2 - x1) * (y3 - y1) - 1LL * (y2 - y1) * (x3 - x1);
}

// verifica daca P(x3,y3) e pe segmentul (x1,y1)-(x2,y2)
inline bool on_segment(int x1, int y1, int x2, int y2, int x3, int y3) {
    if (det_ll(x1,y1,x2,y2,x3,y3) != 0) return false;
    if (min(x1,x2) <= x3 && x3 <= max(x1,x2) && min(y1,y2) <= y3 && y3 <= max(y1,y2))
        return true;
    return false;
}

int main() {
    // citire din/spre fisiere (cerinta)
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);

    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &vx[i], &vy[i]);
    }

    // pentru wrap-around (indexare 1..n, folosim i and j=i+1)
    vx[n+1] = vx[1];
    vy[n+1] = vy[1];

    int ans = 0;
    int px, py;
    while (m--) {
        scanf("%d %d", &px, &py);

        bool inside = false;
        bool onEdge = false;

        // parcurgem muchiile (i -> j = i+1)
        for (int i = 1; i <= n; ++i) {
            int x1 = vx[i], y1 = vy[i];
            int x2 = vx[i+1], y2 = vy[i+1];

            // verificare daca punctul e pe margine
            if (on_segment(x1,y1,x2,y2,px,py)) {
                onEdge = true;
                break;
            }

            // test crossing (segmentul intersecteaza dreapta orizontala y = py?)
            // conditie: y1>py != y2>py  (adica segmentul trece prin intervalul y)
            bool cond = ( (y1 > py) != (y2 > py) );
            if (cond) {
                // calculam coordonata X a intersectiei segment - linie y=py
                // folosing long double pentru siguranta la impartire
                long double xint = x1 + (long double)(x2 - x1) * (py - y1) / (long double)(y2 - y1);
                if ((long double)px < xint) inside = !inside;
            }
        }

        if (onEdge) ++ans;
        else if (inside) ++ans;
    }

    printf("%d", ans);
    return 0;
}