Cod sursa(job #3348860)

Utilizator Matei_AndronacheMatei Andronache Matei_Andronache Data 24 martie 2026 14:47:03
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>
#define mx 67003
#define my 67021
#define int long long
using namespace std;
ifstream in ("poligon.in");
ofstream out ("poligon.out");
struct point{
int x,y;
}v[867];
struct segment{
point a,b;
};
int delta (point a,point b,point c)
{
    return b.x*c.y+c.x*a.y+a.x*b.y-b.x*a.y-c.x*b.y-a.x*c.y;
}
int semn(point a,point b,point c)
{
    int d=delta(a,b,c);
    if (d<0)
        return -1;
    if (d>0)
        return 1;
    return 0;
}
bool intersectie(segment s1,segment s2)
{
    return semn(s1.a,s1.b,s2.a)*semn(s1.a,s1.b,s2.b)<0 && semn(s2.a,s2.b,s1.a)*semn(s2.a,s2.b,s1.b)<0;
}
bool apdretunghi(point a1,point a2,point p)
{
    return min(a1.x,a2.x)<=p.x && p.x<=max(a1.x,a2.x) && min(a1.y,a2.y)<=p.y && p.y<=max(a1.y,a2.y);
}
bool interior(point a,int n)
{

    int nr=0;
    for (int i=1;i<=n;i++)
    {
        int next= i==n? 1 : i+1;
        if (semn(v[i],v[next],a)==0 && apdretunghi(v[i],v[next],a))
        {
            return 1;
        }
    }
    point b={a.x+mx,a.y+my};
    for (int i=1;i<=n;i++)
    {
        int prev= i==1? n : i-1;
        int next= i==n? 1 : i+1;
        if (semn(a,b,v[i])==0)
        {
            if (semn(a,b,v[prev])*semn(a,b,v[next])<0)
                nr++;
        }
        if (intersectie({a,b},{v[i],v[next]}))
            nr++;
    }
    return nr%2;
}
signed main()
{
    int n,m;
    in>>n>>m;
    for (int i=1;i<=n;i++)
    {
        in>>v[i].x>>v[i].y;
    }
    int nr=0;
    for (int i=1;i<=m;i++)
    {
        point a;
        in>>a.x>>a.y;
        nr+=interior(a,n);
    }
    out<<nr;
    return 0;
}