【Note】Minkowski sum / 闵可夫斯基和

概念

闵可夫斯基和是两个欧几里得空间的点集的和，以德国数学家闵可夫斯基命名。我们这样定义点集 $A$ 和 $B$ 的闵可夫斯基和：

$$A+B=\{a+b \ | \ a \in A,b \in B \}$$

类似地，闵可夫斯基差可以被定义为：

$$A-B=\{c \ | \ c +B \subseteq A\} $$

计算方法

考虑点集 $A + B$ 的凸包上的每一个点 $c = a + b$，那么 $a$ 一定位于 $A$ 的凸包上，$b$ 一定位于 $B$ 的凸包上。

这样这个凸包可以看做是 $A$ 凸包上一个定点在 $B$ 凸包上转一圈，所有点出现过的位置的集合。

仔细分析这个转一圈的过程，我们发现 $A + B$ 的凸包就是 $A$ 的凸包的边和 $B$ 的凸包的边按极角排序后首尾相连所得图形。

例题

Nagisa

给你三个凸多边形，在它们内部分别取三个点构成一个三角形，记它的重心为 $G$。

现在有 $m$ 个询问，每次询问给定一个点 $(x_i,y_i)$，判断这个点是否属于合法的 $G$。

Tutorial

设三角形三个顶点分别为 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$，重心 $G$ 为 $(\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3})$。如果我们忽略其中的分母，就可以发现集合 $G$ 实质上是给定凸多边形的闵可夫斯基和。

凸包的闵可夫斯基和还是个凸包，询问就转化成了：给定一个点的坐标，求它是否在一个凸包内。二分即可。

Solutiuon

#include <bits/stdc++.h>
#define min(a,b) (a<b?a:b)
#define mid ((l+r+1)>>1)
#define inf LLONG_MAX
#define ll long long
#define maxn 3001000
int read(){
	int x=0,flag=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if (ch=='-') flag=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
	return x*flag;
}
struct Node{
	int x,y;
	Node operator + (const Node &b) const{
		return (Node){x+b.x,y+b.y};
	}
	Node operator - (const Node &b) const{
		return (Node){x-b.x,y-b.y};
	}
	ll operator * (const Node &b) const{
		return (ll)x*b.y-(ll)y*b.x;
	}
	bool operator < (const Node &b) const{
		int k1=(x<0||(!x&&y<0)),
		k2=(b.x<0||(!b.x&&b.y<0));
		return k1==k2?*this*b<0:k1<k2;
	}
}v[maxn],P1[maxn],P2[maxn],la,F,d;
int n,X,Y,dx,dy,cnt,g1,g2,L1,L2,R1,R2;
void chkmin(int &x,int y){x=x<y?x:y;}
bool find(){
	d=(Node){read()*3-X,read()*3-Y};
	if (d.x<0||d.x>P1[g1].x) return 0;
	if (!d.x) return P2[L2].y<=d.y&&d.y<=P1[L1].y;
	if (d.x==P1[g1].x) return P2[R2].y<=d.y&&d.y<=P1[R1].y;
	int l=1,r=g1;
	while(l<r)
		if (P1[mid].x>d.x) r=mid-1;
		else l=mid;
	bool p1=(d-P1[l])*(P1[l+1]-P1[l])>=0;
	if (!p1) return 0;
	l=1,r=g2;
	while(l<r)
		if (P2[mid].x>d.x) r=mid-1;
		else l=mid;
	return (d-P2[l])*(P2[l+1]-P2[l])<=0;
}
void make(){
	n=read();
	F=la=(Node){X=read(),Y=read()};
	for (int i=2;i<=n;++i)
		d=(Node){read(),read()},
		v[++cnt]=la-d,la=d,
		chkmin(X,d.x),chkmin(Y,d.y);
	v[++cnt]=la-F;dx+=X,dy+=Y;
}
void solve(){
	X=dx,Y=dy;
	std::sort(v+1,v+1+cnt);
	P1[g1=1]=Node(0,0);
	int top=1,y=0;
	for (;top<=cnt;++top){
		if (v[top].x<0) break;
		++g1;P1[g1]=P1[g1-1]+v[top],y=min(y,P1[g1].y);
	}
	P2[g2=1]=P1[g1];
	for (;top<=cnt;++top)
		++g2,P2[g2]=P2[g2-1]+v[top],y=min(y,P2[g2].y);
	Y-=y;
	for (int i=1;i<<1<=g2;++i) std::swap(P2[i],P2[g2+1-i]);
	for (L1=1;P1[L1+1].x==P1[L1].x;++L1);
	for (L1=1;P2[L2+1].x==P2[L2].x;++L2);
	for (R1=g1;P1[R1-1].x==P1[R1].x;--R1);
	for (R2=g2;P2[R2-1].x==P2[R2].x;--R2);
}
int main(){
	make(),make(),make();
	solve();
	int m=read();
	while(m--)
		puts(find()?"YES":"NO");
	return 0;
}