Cod sursa(job #3218399)

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

const int nmax = 800;

const double eps = 1e-9;


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;
}
double dist(point a,point b)
{
    return sqrt((b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y));
}

bool on_line(point x,point a,point b)
{
    return fabs(dist(a,b)-dist(a,x)-dist(b,x))<eps;
}

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;
        int j=1;
        for(;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!=b && a<= x.y && x.y <= b)
                nrinters++;
        }
        if(on_line(x,v[j].st,v[j].dr))
            s++;
        else
            s+=(nrinters%2);
    }
    fout<<s;
}