Bao lồi graham

#include<iostream>
#define nm 50010
using namespace std;
struct point
{
     int x,y;
     bool operator == (point D)const
     {
       	return x==D.x&&y==D.y;
     }
};
point a[nm],p;
int n,m;
long long kc(point a,point b)
{
     long long xx=b.x-a.x;
     long long yy=b.y-a.y;
     return xx*xx+yy*yy;
}
bool behon(point a,point b,point bn)
{
     long long ax,ay,bx,by;
     ax=a.x-bn.x;
     ay=a.y-bn.y;
     bx=b.x-bn.x;
     by=b.y-bn.y;
     if (ay!=0&&by==0)return true;
     if (ay==0||by==0)return false;
     return ax*by>ay*bx;
}
void qs(point a[],int l,int r)
{
     int i=l,j=r;
     point mid=a[(l+r)/2];
     while (i<j)
     {
           while (behon(a[i],mid,a[0]))i++;
           while (behon(mid,a[j],a[0]))j--;
           if (i<=j)swap(a[i++],a[j--]);
     }
     if (i<r)qs(a,i,r);
     if (l<j)qs(a,l,j);
}
int ccw(point p1,point p2,point p3)
{
    long long a1,a2,b1,b2,t;
    a1=p2.x-p1.x;
    a2=p3.x-p1.x;
    b1=p2.y-p1.y;
    b2=p3.y-p1.y;
    t=a1*b2-a2*b1;
    if (t==0)return 0;
    if (t>0)return 1;
    return -1;
}
int graham(point a[],int n)
{
    int m=1;
    for (int i=2;i<=n;i++)
        if (a[m].y>a[i].y)m=i;
    for (int i=1;i<=n;i++)
        if (a[i].y==a[m].y&&a[i].x>a[m].x)m=i;
    swap(a[1],a[m]);
    a[0].x=a[1].x;
    a[0].y=a[1].y-1;
    qs(a,2,n);
    a[++n]=a[1];
    m=2;
    bool ok=true;
    for (int i=3;i<=n;i++)
    {
        ok=true;
        while (ccw(a[m],a[m-1],a[i])>=0)
        {
              if (ccw(a[m],a[m-1],a[i])==0)
              {
                 ok=false;
                 if (kc(a[m],a[m-1])<kc(a[m-1],a[i]))
                    swap(a[m],a[i]);
                 break;
              }
              else
                  m--;
        }
        if (ok)swap(a[++m],a[i]);
    }
    return --m;
}
long long stg(point a,point b,point c)
{
    long long s=(b.x-a.x)*1LL*(b.y+a.y)+(c.x-b.x)*1LL*(c.y+b.y)+(a.x-c.x)*1LL*(a.y+c.y);
    return s>0?s:-s;
}
int namtrong(point p,int l,int r,point b[])
{
     while (r-l>2)
     {
           int mid=(l+r+1)/2;
           int k=ccw(b[1],b[mid],p);
           if (k==0)
           {
              if ((b[1].x-p.x)*(b[mid].x-p.x)<0)return 1;
              return 0;
           }
           if (k==1)l=mid-1;
           if (k==-1)r=mid;
     }
     point x,y,z;
     x=b[1];
     y=b[r];
     z=b[r-1];
     long long k=stg(x,y,z);
     long long t=stg(x,y,p)+stg(x,z,p)+stg(y,z,p);
     if (t>k)return 0;
     int kk=ccw(x,y,p)*ccw(x,z,p)*ccw(y,z,p);
     if (kk!=0)return 1;
     if (p==x||p==y||p==z)return 0;
     if (r==3)
     {
        if (n<=3)return 0;
        if (ccw(x,y,p)==0)
           return 1;
     }
     if (r==n&&ccw(x,z,p)==0)
        return 1;
     if (ccw(x,y,p)==0&&r!=n)
        return 1;
     if (ccw(x,z,p)==0&&r!=3)
        return 1;
     return 0;
}
Ví dụ cách dùng bài METERAIN
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    n=graham(a,n);
    cin>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>p.x>>p.y;
        if (namtrong(p,1,n,a))puts("YES");
        else puts("NO");
    }
    return 0;
}
 
Các bài sẽ áp dụng: METERAIN, HEADQRT, NKLAND, MTRIAREA, MILITARY, KMIX
Code trên của hunterphu