Cod sursa(job #3300278)

Utilizator Carnu_EmilianCarnu Emilian Carnu_Emilian Data 14 iunie 2025 13:55:02
Problema Poligon Scor 20
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 1.67 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;
        /// verificam daca e pe linie
        if (min(y1, y2) <= y && y <= max(y1, y2)) /// se intersecteaza, dar nu stim daca in stanga sau dreapta
        {
            if ((y1 - y2 > 0) && ((1ll * y1*x2 - 1ll * x1*y2 - 1ll * y * (x2 - x1)) < 1ll * x * (y1 - y2))) /// e in stanga
                nr++;
            else if ((y1 - y2 <= 0) && ((1ll * y1*x2 - 1ll * x1*y2 - 1ll * y * (x2 - x1)) > 1ll * x * (y1 - y2))) /// 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;
}