（凸包判断）Codeforces166B Polygons

https://blog.csdn.net/xuh723/article/details/22451957
题意：给出两个图形，判断B是否在A中（不重）（保证AB不重点）
题解：因为时完全包含，所有只要对A，B一起求凸包，判断B中的点是否在凸包上出现即可。
若是没有完全包含这个条件，我们在算法中要将<=改为<（使得B中的点不会在凸包中两个A中点形成的线上），然后进行判断
在不完全包含条件下，若还不保证不重点，可以先将重点去除（无影响）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
 
struct point
{
       double x,y;
       point(){}
       point(double _x,double _y)
       {
                    x=_x;y=_y;
       }
       point operator - (const point &b) const
       {
             return point(x-b.x,y-b.y);
       }
       bool operator < (const point &b) const
       {
            return x<b.x||x==b.x&&y<b.y;
       }
}res[120005],p[120005],pb[20005];
 
int na,nb,n;
 
int dcmp(double x)
{
    return (x>eps)-(x<-eps);
}
 
double cross(point a,point b)
{
       return a.x*b.y-b.x*a.y;
}
 
int andrew()
{
    sort(p,p+n);
    int m=0;
    for (int i=0;i<n;i++)
    {
        while (m>1&&cross(res[m-1]-res[m-2],p[i]-res[m-2])<0) --m;
        res[m++]=p[i];
    }
    int k=m;
    for (int i=n-2;i>=0;--i)
    {
        while (m>k&&cross(res[m-1]-res[m-2],p[i]-res[m-2])<0) --m;
        res[m++]=p[i];
    }
    if (m>1) --m;
    return m;
}
 
int main()
{
    while (scanf("%d",&na)!=EOF)
    {
          for (int i=0;i<na;i++)
          {
              scanf("%lf%lf",&p[i].x,&p[i].y);
          }
          scanf("%d",&nb);
          n=na+nb;
          for (int i=na;i<n;i++)
          {
              scanf("%lf%lf",&p[i].x,&p[i].y);
              pb[i-na]=p[i];
          }
          int m=andrew();
          bool flag=1;
          sort(pb,pb+nb);
          for (int i=0;i<m;i++)
          {
              int tmp=lower_bound(pb,pb+nb,res[i])-pb;//返回第一个大于等于res[i]的pb的下标
              if (dcmp(pb[tmp].x-res[i].x)==0&&dcmp(pb[tmp].y-res[i].y)==0) {flag=0;break;}//如果等于pb则说明B没有完全包含在A内，退出循环
          }
          if (flag==1) printf("YES\n");else printf("NO\n");
    }
    return 0;
}