（凸包判断）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; 
}