Cod sursa(job #2734683)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 1 aprilie 2021 11:30:44
Problema Poligon Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream f("poligon.in");
ofstream g("poligon.out");

struct punct
{
    int x, y;
    //vector<int> vec;
    bool operator<(const punct other) const
    {
        return x < other.x;
    }
} poli[805];
int n, m;

void read()
{
    f>>n>>m;
    for(int i = 0; i<n; i++)
    {
        f>>poli[i].x>>poli[i].y;
        /*poli[i].vec.push_back((i-1+n)%n);
        poli[i].vec.push_back((i+1)%n);*/
    }
    //sort(poli, poli+n);
}

int directie(punct a, punct b, punct c)
{
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int sign(int val)
{
    return val < 0 ? -1 : 1;
}

int verifIntersectie(punct D1P1, punct D1P2, punct D2P1, punct D2P2)
{
    if(sign(directie(D1P1, D1P2, D2P1)) != sign(directie(D1P1, D1P2, D2P2)) && sign(directie(D2P1, D2P2, D1P1)) != sign(directie(D2P1, D2P2, D1P2)))
        return 1;
    return 0;
}

bool pctIntrePcte(punct pct, punct p1, punct p2)
{
    if(p1.x > p2.x)
        swap(p1.x, p2.x);
    if(p1.y > p2.y)
        swap(p1.y, p2.y);
    return p1.x <= pct.x && pct.x <= p2.x && p1.y <= pct.y && pct.y <= p2.y;
}

/*int parc(punct *start; punct *stop)
{
    for(punct *itr = start; itr != stop; itr++)
    {
        verifIntersectie()
    }
}*/

int intersectii(punct pct)
{
    int nrInt = 0;
    if(directie(poli[n-1], poli[0], pct) == 0 && pctIntrePcte(pct, poli[n-1], poli[0]))
        return 1;
    nrInt += verifIntersectie(poli[n-1], poli[0], pct, {100000, pct.y});
    for(int i = 0; i<n-1; i++)
    {
        if(directie(poli[i], poli[i+1], pct) == 0 && pctIntrePcte(pct, poli[i], poli[i+1]))
            return 1;
        nrInt += verifIntersectie(poli[i], poli[i+1], pct, {100000, pct.y});
    }
    return nrInt;
}

void solve()
{
    int nrPcte = 0;
    punct pct;
    for(int i = 0; i<m; i++)
    {
        f>>pct.x>>pct.y;
        /*auto pos = upper_bound(poli, poli+n, pct);*/
        /*if(pos - poli <= n/2)
            parc(poli, pos+1);
        else
            parc(pos, poli+n);*/
        if((intersectii(pct)&1) == 1)
            nrPcte++;
    }
    g<<nrPcte;
}

int main()
{
    read();
    solve();
    return 0;
}