Cod sursa(job #3300276)

Utilizator Carnu_EmilianCarnu Emilian Carnu_Emilian Data 14 iunie 2025 13:35:21
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 1.52 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
typedef long long ll;
typedef long double ld;

const int N = 805;

struct
{
    int x1, y1, x2, y2;
} v[N];
pair<int, int> f[N];
int n, m, x, y, rasp;

/**

1 x1 y1
1 x2 y2
1 x  y
1 x1 y1
1 x2 y2

y(x2 - x1) + x(y1 - y2) = y1*x2 - x1*y2
x(y1 - y2) = y1*x2 - x1*y2 - y(x2 - x1)
x = (y1*x2 - x1*y2  - y(x2 - x1)) / (y1 - y2)

(y1*x2 - x1*y2  - y(x2 - x1)) <= x * (y1 - y2)

*/

bool valid()
{
    /// ray_cast in stanga
    int x1, y1, x2, y2;
    int nr = 0;
    for (int i = 1; i <= n; i++)
    {
        x1 = v[i].x1;
        y1 = v[i].y1;
        x2 = v[i].x2;
        y2 = v[i].y2;
        if (y1 <= y && y <= y2) /// se intersecteaza, dar nu stim daca in stanga sau dreapta
        {
//            cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << x * (y1 - y2) << endl;
            if ((y1*x2 - x1*y2 - y * (x2 - x1)) / (y1 - y2) <= x) /// e in stanga
                nr++;

        }
    }
    return nr % 2 == 1;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        fin >> f[i].first >> f[i].second;
    v[1] = {f[1].first, f[1].second, f[n].first, f[n].second};
    for (int i = 2; i <= n; i++)
        v[i] = {f[i - 1].first, f[i - 1].second, f[i].first, f[i].second};
    while (m--)
    {
        fin >> x >> y;
        if (valid())
            rasp++;
    }
    fout << rasp << '\n';
    fin.close();
    fout.close();
    return 0;
}