前言
前置芝士：计算几何-向量 中的基础芝士。
此文用于纪念自己 A 的第二道黑题。
基本定理
定义
凸多边形：所有内角均在 $[0,\pi]$ 范围内的简单多边形。
凸包：平面上能包含点集中所有点的最小凸多边形为点集的凸包。
闵可夫斯基和：对于两个点集 $A,B$，它们的闵可夫斯基和为：
性质
$S$ 的凸包的边集等于 $A,B$ 两个凸包的边集的并。
由于我懒得画图了，这里用 OI-Wiki 的图做展示：
如图，$W_1=\{A,B,C\},W_2=\{A,D,E,F\}$，其闵可夫斯基和为 $W_3=\{A,C,C’,C’_1,B’_1,B’_2,B\}$。
证明感性理解即可，或者去看 OI-Wiki，性质 2 好像可以用平四证(确信。
例题
思路
第一步直接对 $A,B$ 求个凸包，下文 $A,B$ 就指这个凸包了。
将询问进行一步转换：求是否存在 $\vec a\in A,\vec b\in B$ 使得 $\vec b+\vec v=\vec a$，即 $\vec v=\vec a-\vec b$。
也就是对 $B$ 的点集都取相反数后，求出 $A,B$ 的闵可夫斯基和 $S$，判断 $\vec v$ 是否在这个凸包中即可。
求凸包参考 P2742 【模板】二维凸包 ，用单调栈分别求出上凸壳和下凸壳，再合并即可。
闵可夫斯基和则是对两个凸包的边集按照叉积进行归并排序，见代码。
判断 $\vec v$ 是否在凸包中，可以钦定一个凸包最左边的点作为起点 $p$，得到若干以 $p$ 为起点的向量 $\vec v’=\vec s-\vec p,\vec s\in S,s\neq p$，二分 $\vec v-\vec p$ 被“夹”在哪两条相邻的向量之间，然后判断 $\vec v$ 是否在这个三角形中间即可，即与这两条向量的差没有交。如图：
注意各种边界情况的特判。
代码
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x<<':'<<(x)<<' '
#define dbe(x) cerr<<#x<<':'<<(x)<<endl
#define eb emplace_back
#define ep emplace
#define endl '\n'
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
struct Vec{
using db=long double;
db x,y;
Vec(){}
Vec(db x,db y):x(x),y(y){}
Vec operator+(const Vec&b)const{return {x+b.x,y+b.y};}
Vec operator-(const Vec&b)const{return {x-b.x,y-b.y};}
Vec operator-()const{return {-x,-y};}
db operator%(const Vec&b)const{return x*b.y-y*b.x;}
db len(){return sqrt(x*x+y*y);}
friend istream&operator>>(istream&is,Vec&b){is>>b.x>>b.y;return is;}
friend ostream&operator<<(ostream&os,const Vec&b){os<<b.x<<' '<<b.y;return os;}
};
vector<Vec>convex(vector<Vec>a){
if(a.size()<3)return vector<Vec>();
sort(a.begin(),a.end(),[&](Vec&x,Vec&y){return x.x!=y.x?x.x<y.x:x.y<y.y;});
vector<Vec>c1,c2;
for(Vec v:a){
while(c1.size()>=2&&(c1.back()-c1[c1.size()-2])%(v-c1.back())>=0)c1.pop_back();
c1.eb(v);
while(c2.size()>=2&&(c2.back()-c2[c2.size()-2])%(v-c2.back())<=0)c2.pop_back();
c2.eb(v);
}
c2.pop_back();
reverse(c2.begin(),c2.end());
c2.pop_back();
c1.insert(c1.end(),c2.begin(),c2.end());
return c1;
}
vector<Vec>mkf_sum(const vector<Vec>&a,const vector<Vec>&b){
vector<Vec>E1,E2;
for(int i=1;i<a.size();i++)E1.eb(a[i]-a[i-1]);
E1.eb(a[0]-a.back());
for(int i=1;i<b.size();i++)E2.eb(b[i]-b[i-1]);
E2.eb(b[0]-b.back());
vector<Vec>E;
int p1=0,p2=0;
while(p1<E1.size()||p2<E2.size()){
if(p2==E2.size()||(p1<E1.size()&&E1[p1]%E2[p2]<0))E.eb(E1[p1++]);
else E.eb(E2[p2++]);
}
vector<Vec>V={a[0]+b[0]};
for(Vec v:E)V.eb(V.back()+v);
V.pop_back();
return V;
}
bool in_conv(const Vec&vec,const vector<Vec>&a){
if(a.size()<3)return false;
if(!(a[1]%vec<=0&&vec%a.back()<=0))return false;
int o=lower_bound(a.begin()+2,a.end(),vec,[&](Vec x,Vec y){return y%x>0;})-a.begin();
return (a[o-1]-vec)%(a[o]-vec)<=0;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n,m,q;
cin>>n>>m>>q;
vector<Vec>a(n),b(m),c(q);
for(Vec&v:a)cin>>v;
for(Vec&v:b)cin>>v;
for(Vec&v:c)cin>>v;
for(Vec&v:b)v=-v;
a=convex(a),b=convex(b);
vector<Vec>sum=mkf_sum(a,b);
sum=convex(sum);
for(int i=1;i<sum.size();i++)sum[i]=sum[i]-sum[0];
for(Vec v:c)cout<<in_conv(v-sum[0],sum)<<endl;
return 0;
}细节极多：https://www.luogu.com.cn/discuss/1286442。
为什么闵可夫斯基和的模板是黑。