Cod sursa(job #3359208)

Utilizator rares89_Dumitriu Rares rares89_ Data 26 iunie 2026 03:37:10
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Point {
    long long x, y;
};

int n, m, ans;
vector<Point> p;

long long cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool on_segment(Point a, Point b, Point c) {
    if(cross(a, b, c) != 0) return 0;

    return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}

bool inside(Point q) {
    bool ok = 0;

    for(int i = 0; i < n; i++) {
        Point a = p[i];
        Point b = p[(i + 1) % n];

        if(on_segment(a, b, q)) {
            return 1;
        }

        if((a.y > q.y) != (b.y > q.y)) {
            long double x = a.x + (long double)(q.y - a.y) * (b.x - a.x) / (b.y - a.y);

            if(x > q.x) {
                ok = !ok;
            }
        }
    }

    return ok;
}

int main() {
    fin >> n >> m;

    p.resize(n);

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

    for(int i = 1; i <= m; i++) {
        Point q;
        fin >> q.x >> q.y;

        if(inside(q)) {
            ans++;
        }
    }

    fout << ans << "\n";

    return 0;
}