Cod sursa(job #3218395)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 27 martie 2024 09:35:34
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");

const int nmax = 800;


struct point{
int x;
int y;
}p[nmax + 5],mn,mx;

struct edge{
point st;
point dr;

edge(){}
edge(point a,point b)
{
    if(a.x>b.x)
        swap(a,b);
    else if(a.x==b.x && b.y < a.y)
        swap(a,b);
    st = a;
    dr = b;
}

}v[nmax + 5];

int n,q;

bool inside(point x)
{
    return x.x >=mn.x && x.x<=mx.x && x.y>=mn.y && x.y<=mx.y;
}

int main()
{
    mn.x= 61000;
    mn.y= 61000;
    fin>>n>>q;
    for(int i=1;i<=n;i++){
        fin>>p[i].x>>p[i].y;
        mn.x=min(mn.x,p[i].x);
        mn.y=min(mn.y,p[i].y);
        mx.x=max(mx.x,p[i].x);
        mx.y=max(mx.y,p[i].y);
    }
    for(int i=2;i<=n;i++)
        v[i-1] = edge(p[i],p[i-1]);
    sort(v+1,v+n,[](edge a,edge b){return a.st.x<b.st.x;});
    int s = 0;
    for(int i=1;i<=q;i++)
    {
        point x;
        fin>>x.x>>x.y;
        if(!inside(x))
            continue;
        int nrinters = 0;
        for(int j=1;j<n && v[j].st.x < x.x;j++){
            int a = min(v[j].st.y,v[j].dr.y);
            int b = max(v[j].st.y,v[j].dr.y);
            if(a<x.y && x.y < b)
                nrinters++;
        }
        s+=(nrinters%2);
    }
    fout<<s;
}