
The red figure is the Minkowski sum of blue and green figures.
©Wikipedia
概念
闵可夫斯基和是两个欧几里得空间的点集的和,以德国数学家闵可夫斯基命名。我们这样定义点集 $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;
}