求一个多边形是否完全在另一个凸多边形内。
乍一看，好像要判点在多边形内，但复杂度不允许，仔细一想，可以把两个多边形的点混起来求一个共同的凸包，如果共同的凸包依旧是原来凸包上的点，说明是。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 200010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
int flag;
point(double x=,double y=):x(x),y(y){}
}p[N],ch[N],q[N];
typedef point pointt;
point operator -(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
double cross(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
double mul(point a,point b,point c)
{
return cross(b-a,c-a);
}
double dis(point a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
bool cmp(point a,point b)
{
if(mul(p[],a,b)==)
return dis(p[]-a)<dis(p[]-b);
return mul(p[],a,b)>;
}
int Graham(int n)
{
int i,k = ,top;
point tmp;
for(i = ; i < n; i++)
{
if(p[i].y<p[k].y||(p[i].y==p[k].y&&p[i].x<p[k].x))
k = i;
}
if(k!=)
{
tmp = p[];
p[] = p[k];
p[k] = tmp;
}
sort(p+,p+n,cmp);
ch[] = p[];
ch[] = p[];
top = ;
for(i = ; i < n ; i++)
{
while(top>&&dcmp(mul(ch[top-],ch[top],p[i]))<)
top--;
top++;
ch[top] = p[i];
}
return top;
}
int dot_online_in(point p,point l1,point l2)
{
return !dcmp(mul(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
}
int main()
{
int n,m,i;
cin>>n;
for(i = ; i < n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
p[i].flag = ;
}
cin>>m;
for(i = n ; i < n+m; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
p[i].flag = ;
q[i-n] = p[i];
}
int tn = Graham(n+m);
ch[tn+] = ch[];
int ff = ;
for(i = ; i < m ; i++)
{
if(dot_online_in(q[i],ch[tn],ch[tn+]))
{
ff = ;
//cout<<p[i].x<<" "<<p[i].y<<endl;
break;
}
}
if(!ff)
{
puts("NO");
return ;
}
for(i = ; i <= tn ; i++)
if(ch[i].flag) {ff = ;break;}
if(ff) puts("YES");
else puts("NO");
return ;
}