Cod sursa(job #2500008)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 27 noiembrie 2019 09:34:37
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda guritza Marime 2.76 kb
#include <fstream>
#include <algorithm>
#define x first
#define y second
#define eps 0.00000001
using namespace std;
int n,m,i,j,nr,st,dr,mid,sol,ff,u;
double f[805];
pair <double, double> v[805],w[60005];
struct str{double xf, yf, xs, ys;}d[805];
double det(double X1, double Y1, double X2, double Y2, double X3, double Y3)
{
    return (X2 - X1) * (Y3 - Y1) - (X3 - X1) * (Y2 - Y1);
}
int cmp(str a, str b)
{
    return a.yf+a.ys<b.yf+b.ys;
}
double intersect(pair<double, double> p1, pair<double, double> p2, double x2)
{
    double a, b, c, y2;
    a=p2.y-p1.y;
    b=p1.x-p2.x;
    c=-a*p1.x-b*p1.y;
    y2=(-c-a*x2)/b;
    return y2;
}
double modul(double x)
{
    if(x>0)
    {
        return x;
    }
    return -x;
}
int comp(double x, double y)
{
    if(modul(x-y)<=eps)
    {
        return 0;
    }
    if(x>y)
    {
        return 1;
    }
    return -1;
}
int main()
{
    ifstream cin("poligon.in");
    ofstream cout("poligon.out");
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        cin>>v[i].x>>v[i].y;
        f[i]=v[i].x;
    }
    for(i = 1; i <= m; i++){
        cin>>w[i].x>>w[i].y;
    }
    sort(w+1, w+m+1);
    sort(f+1, f+n+1);
    ff=1;
    for(i=2; i<=n; i++)
    {
        if(comp(f[i],f[ff])!=0)
        {
            ff++;
            f[ff]=f[i];
        }
    }
    u=1;
    while(u<=m&&comp(f[1],w[u].x)==1)
    {
        u++;
    }
    v[n+1]=v[1];
    for(i=1; i <ff; i++)
    {
        nr=0;
        for(j=1; j<=n; j++)
        {
            if(comp(min(v[j].x,v[j+1].x),f[i])!=1&&comp(max(v[j].x,v[j+1].x),f[i+1])!=-1)
            {
                nr++;
                d[nr].xf=f[i];
                d[nr].xs=f[i+1];
                d[nr].yf=intersect(v[j],v[j+1],f[i]);
                d[nr].ys=intersect(v[j],v[j+1],f[i+1]);
            }
        }
        sort(d+1, d+nr+1, cmp);
        while(u<=m&&comp(w[u].x, f[i+1])!=1)
        {
            if(det(d[1].xf,d[1].yf,d[1].xs,d[1].ys,w[u].x,w[u].y)<-eps||det(d[nr].xf,d[nr].yf,d[nr].xs,d[nr].ys,w[u].x,w[u].y)>eps)
            {
                u++;
                continue;
            }
            st=1;
            dr=nr;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                double det2=det(d[mid].xf,d[mid].yf,d[mid].xs,d[mid].ys,w[u].x,w[u].y);
                if(det2<-eps)
                {
                    dr=mid-1;
                }
                else
                {
                    st=mid+1;
                }
            }
            if(modul(det(d[dr].xf, d[dr].yf, d[dr].xs, d[dr].ys, w[u].x, w[u].y))<=eps||dr%2==1)
            {
                sol++;
            }
            u++;
        }
    }
    cout<<sol<<"\n";
    return 0;
}