Cod sursa(job #3222998)

Utilizator unomMirel Costel unom Data 12 aprilie 2024 10:01:46
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>

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()
{
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    in>>n>>m;

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

    v[0] = v[n];

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

        int ok = 0;
        for(int i = 0; i<n; i++)
        {
            if(pctseg(v[i].first, v[i].second, v[i + 1].first, v[i + 1].second, x, y))
            {
                ok = 1;
                break;
            }
        }

        if(ok == 1)
        {
            ans++;
            //out<<"DA \n";
            continue;
        }

        while(1)
        {
            xv = 60002 + uniform_int_distribution<int>(0, 59999)(rng);
            yv = 60002 + uniform_int_distribution<int>(0, 59999)(rng);

            inter = 0;
            test = 1;

            for(int i = 0; i<n; i++)
            {
                if(pctseg(x, y, xv, yv, v[i].first, v[i].second) || pctseg(x, y, xv, yv, v[i + 1].first, v[i + 1].second))
                {
                    test = 0;
                    break;
                }

                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 == 0 && d2 == 0)
                {
                    test = 0;
                    break;
                }

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

            if(test == 1)
            {
                if(inter % 2 == 1)
                {
                    ans++;
                    //out<<"DA \n";
                }
                else
                {
                    //out<<"NU \n";
                }
                break;
            }
        }
    }

    out<<ans;

    return 0;
}