Cod sursa(job #3223008)

Utilizator unomMirel Costel unom Data 12 aprilie 2024 10:11:32
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>

using namespace std;

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];

    int x, y, xv, yv, 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++;
            continue;
        }


            xv = 104867;
            yv = 142569;

            inter = 0;

            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(inter % 2 == 1)
                {
                    ans++;
                }



    }

    out<<ans;

    return 0;
}