Steven_Meng's Blog

对于两个凸包$A,B$，把它们的最下面的点平移到$(0,0)$的位置，对于$\vec a \in A,\vec b \in B$，$\vec a+\vec b$构成的凸包就是两个凸包的闵可夫斯基和。

如何理解呢？

（图片来自洛谷）

对于这张图，顶点已经平移到$(0,0)$，先固定$\vec a$，现在我们把另一个凸包的顶点平移到$\vec a$代表的点，发现另一个凸包现在代表的区域是$\vec a + \vec b$，于是，我们把另一个凸包的顶点平移到第一个凸包内的点上，把平移后的区域全部涂上颜色，最后所有有颜色的区域就是他们俩的闵可夫斯基和。

继续观察，发现这个大凸包上面有7条边，第一个凸包有3条边，第二个凸包有4条边，仿佛暗示着大凸包的所有边是第一个和第二个凸包所有边首尾相连形成的。

怎么首尾相连，观察到是按照极角大小从小到大依次首尾相连形成的。

于是我们有了一个奇妙的结论：把两凸包的边极角排序后直接顺次连起来就是闵可夫斯基和。

实现起来非常容易，因为两个凸包的边本来就是有序的，只要把两个凸包的边归并一下即可。

例题：

P4557 [JSOI2018]战争

九条可怜最可爱了！

假设移动的向量是$\vec d$，第二个凸包里面的向量$\vec b$变成$\vec b +\vec d$

于是题目要求的就是是否存在$\vec a,\vec b$，使得$\vec a = \vec b + \vec d$

简单移项，变成$\vec d = \vec a -\vec b$

于是就是询问$\vec d$是否属于$\\{ \vec c | \vec c = \vec a - \vec b\\}$

这个就是把第二个凸包的所有点按照$(0,0)$对称，再求闵可夫斯基凸包和。

#include <bits/stdc++.h>
#define MAXN 100005
#define ll long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
struct Point{
    ll x,y;
};
inline ll operator * (const Point &A,const Point &B){
    return A.x*B.y-A.y*B.x;
}
inline Point operator - (const Point &A,const Point &B){
    return Point{A.x-B.x,A.y-B.y};
}
inline Point operator + (const Point &A,const Point &B){
    return Point{A.x+B.x,A.y+B.y};
}
inline double dis(const Point &A){
    return sqrt(A.x*A.x+A.y*A.y);
}
inline bool operator < (const Point &A,const Point &B){
    ll ans=(A*B);
    if (ans!=0) return ans>0;
    else return dis(A)<dis(B);
}
Point stk[MAXN];
int top;
struct Convex{
    Point A[MAXN];
    int tot,pos;
    Convex(){pos=1;memset(A,0,sizeof(A));tot=0;}
    Point & operator[] (int pos){return A[pos];}
    inline void Insert(Point P){
        A[++tot]=P;
        if (A[pos].x>P.x||(A[pos].x==P.x&&A[pos].y>P.y)) pos=tot;
    }
    inline void Build(){//建立凸包
        swap(A[1],A[pos]);
        for (register int i=2;i<=tot;++i) A[i]=A[i]-A[1];
        sort(A+2,A+1+tot);
        for (register int i=2;i<=tot;++i) A[i]=A[i]+A[1];
        top=0;
        for (register int i=1;i<=tot;++i){
            while (top>1&&(stk[top]-stk[top-1])*(A[i]-stk[top-1])<=0) top--;
            stk[++top]=A[i];
        }
        memcpy(A,stk,sizeof(A));
        tot=top;
    }
    inline Point Top(){//获取凸包上面最后一个元素
        return A[tot];
    }
}F,S;
Point s1[MAXN],s2[MAXN];
Point temp;
inline Convex Minkowski(Convex X,Convex Y){
    int n=X.tot,m=Y.tot;
    for (register int i=1;i<n;++i) s1[i]=X[i+1]-X[i];
    s1[n]=X[1]-X[n];
    for (register int i=1;i<m;++i) s2[i]=Y[i+1]-Y[i];
    s2[m]=Y[1]-Y[m];
    Convex Ans;
    Ans.Insert(X[1]+Y[1]);
    int j=1,k=1;//凸包归并
    while (j<=n&&k<=m) Ans.Insert(Ans.Top()+(s1[j]*s2[k]>=0?s1[j++]:s2[k++]));
    while (j<=n) Ans.Insert(Ans.Top()+s1[j++]);
    while (k<=m) Ans.Insert(Ans.Top()+s2[k++]);

	temp=Ans[1];
    for (register int i=Ans.tot;i>=1;--i){
        Ans[i]=Ans[i]-temp;
    }
    return Ans;
}
Convex A;
inline bool Inside(Point P){//判断P是否在凸包内
    if (P*A[1]>0||A.Top()*P>0) return false;
    int pos=lower_bound(A.A+1,A.A+1+A.tot,P)-A.A-1;
    return (P-A[pos])*(A[pos%A.tot+1]-A[pos])<=0;
}
int main(){
    int n=read(),m=read(),q=read();
    for (register int i=1;i<=n;++i){
        int x=read(),y=read();
        F.Insert(Point{x,y});
    }
    for (register int i=1;i<=m;++i){
        int x=read(),y=read();
        S.Insert(Point{-x,-y});
    }
    F.Build(),S.Build();
    A=Minkowski(F,S);
    A.Build();
    while (q--){
        int dx=read(),dy=read();
        puts(Inside(Point{dx,dy}-temp)?"1":"0");
    }
}

是不是感觉九条题目就是这样？