Cod sursa(job #3223015)

Utilizator unomMirel Costel unom Data 12 aprilie 2024 10:17:22
Problema Poligon Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>

using namespace std;

#define int long long

ifstream in("poligon.in");
ofstream out("poligon.out");
int n, m, ans;
pair<int, int> v[805];

int det(int x1, int y1, int x2, int y2, int x3, int y3)
{
    return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}

int pctseg(int x1, int y1, int x2, int y2, int x3, int y3)
{
    int d = det(x1, y1, x2, y2, x3, y3);

    if(d == 0 && x3 >= min(x1, x2) && x3 <= max(x1, x2) && y3 >= min(y1, y2) && y3 <= max(y1, y2))
    {
        return 1;
    }

    return 0;
}

signed main()
{
    in>>n>>m;

    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;
    }

    v[0] = v[n];

    long long x, y, xv, yv, inter, d1, d2, d3, d4;
    while(m--)
    {
        in>>x>>y;

        xv = 69696;
        yv = 71717;

        inter = 0;

        for(int i = 0; i<n; i++)
        {
            d1 = det(v[i].first, v[i].second, v[i + 1].first, v[i + 1].second, x, y);
            d2 = det(v[i].first, v[i].second, v[i + 1].first, v[i + 1].second, xv, yv);
            d3 = det(x, y, xv, yv, v[i].first, v[i].second);
            d4 = det(x, y, xv, yv, v[i + 1].first, v[i + 1].second);


            if(d1 * d2 < 0 && d3 * d4 < 0)
            {
                inter++;
            }
        }

        if(inter % 2 == 1)
        {
            ans++;
        }
    }

    out<<ans;

    return 0;
}