前言
这篇东西大部分都是在瞎bb，大佬们可以选择不看。
需要先学一点点线性代数的内容。
由于本人太菜，这篇博客只会讨论二维的情况。
由于本人太懒，因此会缺少一些示意图。
向量
点积/数量积
一般用 \(\vec a \cdot \vec b\) 表示，有 \(\vec a \cdot \vec b = |\vec a||\vec b|\cos \left<\vec a, \vec b\right> = x_ax_b+y_ay_b\)
其中 \(\left<\vec a, \vec b\right>\) 表示 \(\vec a, \vec b\) 的夹角大小。
简单的应用：
判断向量垂直：\(\vec a \bot \vec b \Longleftrightarrow \vec a\cdot \vec b = 0\)
判断向量贡献：\(\vec a // \vec b \Longleftrightarrow \vec a\cdot \vec b = |\vec a||\vec b|\)
判断向量夹角：\(\cos\left<\vec a, \vec b\right> = \frac{\vec a \cdot \vec b}{|\vec a||\vec b|}\)
叉积
\[\mathrm{Cross}(\vec a,\vec b) = |\vec a||\vec b|\sin\left<\vec a, \vec b\right> = x_ay_b-x_by_a \]非常有用，可以用于判断 \(\vec a\) 旋转到 \(\vec b\) 选用顺指针转还是逆时针转。同时，两个向量的叉积的绝对值等于这两个向量夹成的平行四边形的面积。
\(\mathrm{PS}\)：叉积实际上是一个二阶行列式。
接下来我们将叉积简写成 \(\vec a\times \vec b\) 。
叉积拥有分配律，结合律（和行列式相同）。
叉积用于判断旋转的具体操作如下：
- 叉积 \(>0\)，则从 \(\vec a\) 旋转到 \(\vec b\) ，用逆时针的旋转角度最小。
- 叉积 \(<0\)，则从 \(\vec a\) 旋转到 \(\vec b\) ，用顺时针的旋转角度最小。
- 叉积 \(=0\)，则 \(\vec a, \vec b\) 共线。
此外，叉积可以用判断一个点 \(P\) 在直线 \(l\) 的哪一侧。具体而言，随便找到直线上的两个不同的点 \(A,B (A,B\in l)\)，然后作向量差 \(\vec a = A - B, \vec b = P - B\)，判断 \(\vec a\times \vec b\) 的正负。
极坐标系
不同于普通的二维直角坐标系，我们用角度 \(\theta\) （极角）和离原点（极点）的距离 \(r\) （极距）描述一个空间中的位置 \((r,\theta)\) 。转换到普通的直角坐标系，就变成了 \((r\cos \theta, r\sin \theta)\) 。
极坐标系描述一些图形的时候比较便利，比如对于单位圆 \(C: x^2+y^2=1\) ，变成极坐标方程就是 \(r(\theta) = 1\) 。
为了将平面直角坐标系的信息转化为极坐标系的信息，我们需要使用特殊的三角函数：\(\mathrm{atan2}\)，这个函数已经内置于 \(\rm C++\) 的 cmath 中。
\(\theta = \mathrm{atan2}(y,x), r = \frac{x}{\cos \theta}\)。
基本操作
绕某点旋转
给定两个点 \(P_1, P_2\) 和一个旋转角度 \(\theta\)，求 \(P_1\) 绕 \(P_2\) 顺时针旋转 \(\theta\) 后得到的点 \(P_3\) 。
这里直接给出公式吧：
\[\begin{aligned} x_{P_3}& = \left(x_{P_1} - x_{P_2}\right)\cos \theta - \left(y_{P_1} - y_{P_2}\right)\sin \theta + x_{P_2}\\ y_{P_3}& = \left(x_{P_1} - x_{P_2}\right)\sin \theta + \left(y_{P_1} - y_{P_2}\right)\cos \theta + y_{P_2}\\ \end{aligned} \]求直线交点
分别给定两条直线 \(l_1, l_2\) 上的两个点：\(A,B,C,D (A,B\in l_1, C,D\in l_2)\) ，求出交点 \(P (P = l_1\cap l_2)\) 。
稍微给个图：
作图说明：\(AE//BD, DE//AB,CF//AB,EF//CD, AE\cap DE = E, EF\cap CF = F\)。
容易得到：
\[\begin{aligned} S_{\text{四边形}ABDE} = \left|\overrightarrow{BA}\times \overrightarrow{BD}\right|\\ S_{\text{四边形}CDEF} = \left|\overrightarrow{CD}\times \overrightarrow{CF}\right|\\ \end{aligned} \]因为 \(_{\text{四边形}ABDE},S_{\text{四边形}CDEF}\) 共底，因此面积比等于高比，进而得到
\[\frac{\left|\overrightarrow{DP}\right|}{\left|\overrightarrow{DC}\right|} = \frac{S_{\text{四边形}ABDE}}{S_{\text{四边形}CDEF}} = \frac{\left|\overrightarrow{BA}\times \overrightarrow{BD}\right|}{\left|\overrightarrow{CD}\times \overrightarrow{CF}\right|} \]因此可以得到：
\[\overrightarrow{DP} = \frac{\left|\overrightarrow{BA}\times \overrightarrow{BD}\right|}{\left|\overrightarrow{CD}\times \overrightarrow{CF}\right|}\times \overrightarrow{DC} \]接着就能得到 \(P\) 的坐标了：
\[P = D + \frac{\left|\overrightarrow{BA}\times \overrightarrow{BD}\right|}{\left|\overrightarrow{CD}\times \overrightarrow{CF}\right|}\times (D - C) \]凸包
判断点和凸多边形的关系
运用叉积可以判断一个点是否在凸包中。
具体而言，假设需要判断一个点 \(P\) 是否在凸包中，可以逆时针扫描凸包，对于每一条边 \(A_{i-1}A_i\) ，都需要满足 \((P-A_{i-1})\times \overrightarrow{A_{i-1}A_i} \ge 0\) 。这个算法显然是 \(O(\text{凸包边数})\) 的，需要进行一点优化。
Algorithm 1
做一条直线 \(y = y_P\) ，这条直线和凸包的交点为 \(P_1, P_2\)（当交点小于一个的时候，显然 \(P\) 不在凸包中），我们可以直接判断 \(x_P\) 和 \(P_1, P_2\) 的大小关系，当且仅当 \(x_{P_1}\leq x_P\leq x_{P_2}\) 的时候，\(P\) 在凸包中。
算法瓶颈显然在找交点的部分，本人不太懂。
Algorithm 2
运用叉积，设凸多边形按逆时针转组成的点序列为 \(P_{1\dots m}\) ，那么作 \(m-1\) 条射线，其中第 \(i\) 条射线 \(L_i\) 的的起点为 \(P_1\)，方向为向量 \(\overrightarrow{P_1P_{i+1}}\) 的方向，这个操作实际上就是将多边形三角剖分。
显然，当 \(P\) 在 \(L_1\) 右侧或者 \(L_{m-1}\) 左侧，那么 \(P\) 不在凸包中。接着，可以用二分的方式找到点 \(P\) 被夹在哪两条射线中，假设被夹在射线 \(L_i, L_{i+1}\) 之间，用叉积判断一下这个点是否在 \(\overrightarrow{P_{i+1}P_{i+2}}\) 的左侧（或者就在向量所在的线段上），如果是，那么 \(P\) 在凸多边形中，否则就不在。
bool jdg_in_hull(Vector2* hl/*凸多边形按照逆时针的序列*/, int hl_sz, Vector2 p) {
if (cross(p - hl[1], hl[hl_sz] - hl[1]) < 0 || cross(p - hl[1], hl[2] - hl[1]) > 0) return false;
int l = 2, r = hl_sz - 1, bl = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (cross(hl[mid] - hl[1], p - hl[1]) > 0) bl = mid, l = mid + 1;
else r = mid - 1;
}
return cross(p - hl[bl], hl[bl + 1] - hl[bl]) <= 0;
}
找凸包
\(\Rightarrow \rm luogu\) 的模版题
给定 \(n\) 个平面上的点，我们选择找到其中的一些点，其围成的凸多边形可以将这 \(n\) 个点包起来（在凸包内/在凸包上）。
Algorithm 1: Andrew算法
将所有点按照横坐标为第一关键字，纵坐标为第二关键字从小到大排序，用一个栈维护凸壳，维护条件可以是满足栈中相邻的点的叉积都是正数，先顺序扫一遍所有点找到下凸壳，然后从栈中最后一个点出发，按逆序再扫一遍点，得到上凸壳，然后就能得到整个凸包了。
struct Vector2 {
LD x, y;
Vector2(LD x = 0, LD y = 0) : x(x), y(y) {}
} p[maxn], stk[maxn << 1];
int stk_tp;
inline Vector2 operator + (Vector2 a, Vector2 b) { return Vector2(a.x + b.x, a.y + b.y); }
inline Vector2 operator - (Vector2 a, Vector2 b) { return Vector2(a.x - b.x, a.y - b.y); }
inline bool operator < (Vector2 a, Vector2 b) {
return (a.x == b.x ? a.y < b.y : a.x < b.x);
}
inline LD len(Vector2 a) { return sqrt(a.x * a.x + a.y * a.y); }
inline LD cross(Vector2 a, Vector2 b) { return a.x * b.y - a.y * b.x; }
void find_hull() {
sort(p + 1, p + 1 + n);
stk[1] = p[1], stk[stk_tp = 2] = p[2];
for (int i = 3; i <= n; i++) {
while (stk_tp > 1 && cross(p[i] - stk[stk_tp - 1], stk[stk_tp] - stk[stk_tp - 1]) > 0)
stk_tp--;
stk[++stk_tp] = p[i];
}
stk[++stk_tp] = p[n - 1];
for (int i = n - 2; i >= 1; i--) {
while (stk_tp > 1 && cross(p[i] - stk[stk_tp - 1], stk[stk_tp] - stk[stk_tp - 1]) > 0)
stk_tp--;
stk[++stk_tp] = p[i];
}
//此时栈中的点就是凸包按逆时针转的点，p[1]被计算两次
}
Algorithm 2: Graham 扫描法
使用极坐标系。
按横坐标为第一关键字，纵坐标为第二关键字找到最小的点，然后以这个点为极点，然后将剩余的点按照极角从小到大排序，依然用栈维护凸包，顺序扫一遍就行了。
//这是大佬 klii(tjp) 写的
using namespace std;
const int N = 2e5 + 5;
struct Vec {
double x, y;
}p[N];
int n, stk[N], top;
Vec getvec(int a, int b) {
return (Vec){p[b].x - p[a].x, p[b].y - p[a].y};
}
double Cross(Vec a, Vec b) {
return a.x * b.y - a.y * b.x;
}
double dist(int a, int b) {
return sqrt((p[a].x - p[b].x) * (p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y));
}
bool cmp(Vec a, Vec b) {
if (a.x == p[1].x && b.x == p[1].x) return a.y < b.y;
double t1 = atan2(a.y - p[1].y, a.x - p[1].x);
double t2 = atan2(b.y - p[1].y, b.x - p[1].x);
return t1 == t2 ? a.x < b.x : t1 < t2;
}
int main() {
scanf("%d", &n);
int idx = 1;
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &p[i].x, &p[i].y);
if (p[i].y < p[idx].y || p[i].y == p[idx].y && p[i].x < p[idx].x) idx = i;
}
swap(p[1], p[idx]);
sort(p + 2, p + 1 + n, cmp);
stk[top = 1] = 1;
for (int i = 2; i <= n; i++) {
while (top > 1 && Cross(getvec(stk[top - 1], stk[top]), getvec(stk[top], i)) < 0) top--;
stk[++top] = i;
}
double ans = 0;
stk[top + 1] = stk[1];
for (int i = 1; i <= top; i++) ans += dist(stk[i], stk[i + 1]);
printf("%.2lf", ans);
return 0;
}
旋转卡壳
读音多样的算法，可以用于求出凸包的直径（凸包中最远两点的距离）。
\(\Rightarrow \rm luogu\) 的模版题
可以想到一种简单的暴力：首先枚举一条凸包上的边，然后找到距离这条边最远的点，然后用这条边的两个端点和那个点连线，更新答案。求距离的方法可以是行列式求出面积，然后除去边的长度。
而旋转卡壳实际上就是将上面的暴力优化一下而已。考虑顺时针考虑边 \(l\) ，假设当前考虑了第 \(i\) 条边，而此时最远点为 \(p_j\) ，接下来考虑第 \(i + 1\) 条边，最远点显然会是 \(p_j\) 顺时针移动一定次数到达的点，而不会逆时针移动，这显然不优。
考虑顺时针移动的总次数，可以发现每个凸包上的点只会被经过 \(O(1)\) 次，因此总的时间复杂度显然是 \(O(n)\) 的。
//PS：早期码风
int operator * (Vector2 a, Vector2 b) {
return a.x * b.y - a.y * b.x;
}
LL dist(Vector2 a, Vector2 b) {
Vector2 c = a - b;
return c.x * c.x + c.y * c.y;
}
void find_hull() {
sort(a + 1, a + 1 + n);
stk[tp = 1] = a[1];
for (int i = 2; i <= n; i++) {
while (tp > 1 && (stk[tp] - stk[tp - 1]) * (a[i] - stk[tp - 1]) <= 0)
tp--;
stk[++tp] = a[i];
}
int tmp = tp;
for (int i = n - 1; i >= 1; i--) {
while (tp > tmp && (stk[tp] - stk[tp - 1]) * (a[i] - stk[tp - 1]) <= 0)
tp--;
stk[++tp] = a[i];
}
for (int i = 1; i <= tp; i++) p[i] = stk[i];
p_sz = tp - 1;
}
Vector2 cc;
LL diame;
void calc_diame() {
diame = 0;
if (p_sz == 2) {
cc = (p[1] + p[2]) / 2;
diame = dist(p[1], p[2]);
return ;
}
int to = 2;
for (int i = 1; i <= p_sz; i++) {
//移动
while ((p[i+1]-p[i])*(p[to]-p[i]) < (p[i+1]-p[i])*(p[to+1]-p[i]))
to = to % p_sz + 1;
//更新答案
if (diame < dist(p[to], p[i])) {
diame = dist(p[to], p[i]);
cc = (p[to] + p[i]) / 2;
}
if (diame < dist(p[to], p[i+1])) {
diame = dist(p[to], p[i+1]);
cc = (p[to] + p[i+1]) / 2;
}
}
}
例题： P3187 [HNOI2007]最小矩形覆盖
可以想到答案的矩形的其中一条边一定和凸包上某一条边共线。
因此可以用旋转卡壳求出每一条边 \(l\) 对应的最优矩形的高度，至于宽度，显然是由一个和 \(l\) 组成的点积最小的点和一个 \(l\) 组成的点积最大的点确定，显然，这两个点也可以用类似旋转卡壳的方式维护。
void calc_ans() {
int j1 = 2, j2 = 2, j3 = 1;
stk_tp--;
for (int i = 1; i <= stk_tp; i++) {
while (cross(stk[j1 + 1] - stk[i], stk[i + 1] - stk[i]) >= cross(stk[j1] - stk[i], stk[i + 1] - stk[i]))
j1 = j1 % stk_tp + 1;
while (dot(stk[j2 + 1] - stk[i + 1], stk[i] - stk[i + 1]) <= dot(stk[j2] - stk[i + 1], stk[i] - stk[i + 1]))
j2 = j2 % stk_tp + 1;
if (i == 1) j3 = j1;
while (dot(stk[j3 + 1] - stk[i], stk[i + 1] - stk[i]) <= dot(stk[j3] - stk[i], stk[i + 1] - stk[i]))
j3 = j3 % stk_tp + 1;
LD len_i = len(stk[i + 1] - stk[i]);
LD l = dot(stk[j2] - stk[i], stk[i + 1] - stk[i]) / len_i,
r = dot(stk[j3] - stk[i + 1], stk[i] - stk[i + 1]) / len_i,
u = cross(stk[j1] - stk[i], stk[i + 1] - stk[i]) / len_i;
l = abs(l), r = abs(r), u = abs(u);
LD S = (l + r - len_i) * u;
if (S < ans) {
ans = S;
//PS : 这里的点是顺时针的，要倒着输出
ap1 = stk[i + 1] - (r / len_i) * (stk[i + 1] - stk[i]),
ap2 = ap1 + ((l + r - len_i) / len_i) * (stk[i + 1] - stk[i]),
ap3 = ap2 + (u / len(stk[j2] - ap2)) * (stk[j2] - ap2),
ap4 = ap3 - ((l + r - len_i) / len_i) * (stk[i + 1] - stk[i]);
}
}
}
半平面交
半平面：给定一条在平面上的直线 \(l\) ，在直线上方/下方的所有点的点集被称为半平面，一半定义形式为：
\[\begin{aligned} &\{(x,y) \mid Ax+By+C\leq 0\}\\ &\{(x,y) \mid [(x,y)-A]\times [B,A]\leq 0, A,B\in l\} \end{aligned} \]这里的 \(\leq\) 可以换成 \(<,>,\ge\) 。
两种表示方式各有优势，其中求多个凸多边形的并相关信息的时候常用第二种。
这里设定所有半平面都是直线左侧的（即不等号为 $\ge $）。
这里先将所有直线都找出来，然后按照极角从小到大排序，这里用极角代替斜率可以避免讨论斜率不存在的情况。
接着用一个双端队列 \(\rm deque\) 维护信息。
考虑加入一条新的直线 \(l\) ，其中队尾的直线为 \(l_1\), 队尾上一条直线是 \(l_2\) ，其交点为 \(P\) ，如果 \(P\) 在 \(l\) 的右侧，那么加上 \(l\) 后半平面的交等价于加上 \(l\) ，然后删除 \(l_1\) 的交，因此可以直接将 \(l_1\) 弹出（这里直接用 \(\rm dalao~klii\) 的图）；如果 \(P\) 在 \(l\) 的左侧，那么 \(l_1\) 无法舍去。(\(l\rightarrow \text{红}, l_1\rightarrow \text{绿}, l_2\rightarrow \text{蓝}\))
同时 \(l\) 还可能对队首产生影响：(\(l\rightarrow \text{红},\text{队首}\rightarrow \text{绿},\text{队首下一个}\rightarrow \text{蓝}\))
因此当队头的交点在 \(l\) 的右侧的时候还需要弹出队头。
struct Line {
Vector2 a, b; LD k;
Line(Vector2 a = Vector2(0, 0), Vector2 b = Vector2(0, 0), LD k = 0) : a(a), b(b), k(k) {}
} l[maxn], tl[maxn];
inline LD get_slope(Vector2 a) { return atan2(a.y, a.x); }
bool cmp(Line a, Line b) {
return abs(a.k - b.k) > EPS ? a.k < b.k : cross(b.a - a.a, a.b - a.a) > EPS;
}
inline bool chk_right(Line a, Vector2 b) { return cross(b - a.a, a.b - a.a) > EPS; }
Vector2 its[maxn];
inline Vector2 get_intersect(Line a, Line b) {
return a.a + (cross(b.a - a.a, b.b - b.a) / cross(a.b - a.a, b.b - b.a)) * (a.b - a.a);
}
int q[maxn], ql, qr;
LD calc_intersect_S() {
sort(l + 1, l + 1 + m, cmp);
ql = 1, qr = 0; int cnt;
tl[cnt = 1] = l[1];
for (int i = 2; i <= m; i++) if (abs(l[i].k - l[i - 1].k) > EPS)
tl[++cnt] = l[i];
for (int i = 1; i <= cnt; i++) {
while (ql < qr && chk_right(tl[i], its[qr])) qr--;
while (ql < qr && chk_right(tl[i], its[ql + 1])) ql++;
q[++qr] = i;
if (ql < qr) its[qr] = get_intersect(tl[q[qr - 1]], tl[q[qr]]);
}
while (ql < qr && chk_right(tl[q[ql]], its[qr])) qr--;
its[ql] = get_intersect(tl[q[ql]], tl[q[qr]]);
LD res = 0;
for (int i = ql + 2; i <= qr; i++) res += cross(its[i - 1] - its[ql], its[i] - its[ql]);
return res / 2;
}
Vector2 pls[maxn];
int main() {
int n, mi; scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &mi);
for (int j = 1; j <= mi; j++) scanf("%Lf %Lf", &pls[j].x, &pls[j].y);
pls[mi + 1] = pls[1];
for (int j = 1; j <= mi; j++)
l[++m] = Line(pls[j], pls[j + 1], get_slope(pls[j + 1] - pls[j]));
}
printf("%.3Lf\n", calc_intersect_S());
return 0;
}
给一道简单例题：\(\Rightarrow\) P3222 [HNOI2012]射箭
闵可夫斯基和
给个定义：设 \(A,B\) 为两个点集，其闵可夫斯基和为 \(A+B\) 。运算规则如下：
\[C=A+B=\{a+b \mid a\in A, b\in B\} \]可以这么理解：将 \(B\) 中每个点按照 \(A\) 中每个点偏移得到的点集。
对于任意两个点集的闵可夫斯基和的时间复杂度貌似只能做到 \(O(|A||B|)\) 。但是如果是求闵可夫斯基和的凸包，则可以做到 \(O(|A\text{ 的凸包点数}|+|B\text{ 的凸包点数}|)\) 。
设点集 \(A\) 的凸包多边形为 \(H(A)\) 。
首先，求出 \(H(A),H(B)\) 。分别选定 \(H(A),H(B)\) 中的坐标最小（这里选用横坐标最小情况下纵坐标最小）的点 \(P_1, P_2\) ，那么 \(H(A+B)\) 中坐标最小的点显然是 \(P_1+P_2\) 。
然后通过画图找规律可以发现，\(H(A+B)\) 中的所有边都是在 \(H(A),H(B)\) 中出现过的，因此将 \(H(A),H(B)\) 中的边逆时针组成一个序列，然后按照极角从小到大归并，即可得到 \(H(A+B)\) 。
int hl1_sz, hl2_sz, shl_sz;
struct Vector2 { ... } p1[maxn], p2[maxn], hl1[maxn], hl2[maxn], l[maxn], shl[maxn];
...
bool hull_cmp(Vector2 a, Vector2 b) { return a.x != b.x ? a.x < b.x : a.y < b.y; }
Vector2 t[maxn], t2[maxn]; int tsz;
void get_hull(Vector2* p, int n, Vector2* hl, int& cnt) {
sort(p + 1, p + 1 + n, hull_cmp), t[1] = p[1], t[tsz = 2] = p[2];
for (int i = 3; i <= n; i++) {
while (tsz > 1 && cross(p[i] - t[tsz - 1], t[tsz] - t[tsz - 1]) >= 0) tsz--;
t[++tsz] = p[i];
}
t[++tsz] = p[n - 1];
for (int i = n - 2; i >= 1; i--) {
while (tsz > 1 && cross(p[i] - t[tsz - 1], t[tsz] - t[tsz - 1]) >= 0) tsz--;
t[++tsz] = p[i];
}
cnt = tsz - 1;
for (int i = 1; i <= tsz; i++) hl[i] = t[i];
}
//这里可能会有一些重复边或者点，需要对shl再做一次凸包才能得到 H(A+B)
void Minkowski(Vector2* hl1, Vector2* hl2, int hl1_sz, int hl2_sz, Vector2* shl, int& shl_sz) {
int p1 = 0, p2 = 0;
shl[shl_sz = 1] = hl1[1] + hl2[1];
for (int i = 1; i < hl1_sz; i++) t[i] = hl1[i + 1] - hl1[i];
for (int i = 1; i < hl2_sz; i++) t2[i] = hl2[i + 1] - hl2[i];
t[hl1_sz] = hl1[1] - hl1[hl1_sz], t2[hl2_sz] = hl2[1] - hl2[hl2_sz];
while (p1 < hl1_sz || p2 < hl2_sz) {
Vector2 cho;
if (p1 == hl1_sz) cho = t2[++p2];
else if (p2 == hl2_sz) cho = t[++p1];
else cho = (cross(t[p1 + 1], t2[p2 + 1]) >= 0 ? t[++p1] : t2[++p2]);
shl[shl_sz + 1] = cho + shl[shl_sz], ++shl_sz;
}
}
Minkowski(hl1, hl2, hl1_sz, hl2_sz, shl, shl_sz);
get_hull(shl, shl_sz, hl1, hl1_sz);
// hl1[1...hl1_sz] 就是最终的凸包
例题
P4557 [JSOI2018]战争
给个简介的题意：给定两个点集 \(A,B\) ，进行 \(Q\) 次询问，每次询问给定一个偏移向量 \((dx, dy)\) ，将 \(B\) 中所有的向量按这个偏移向量偏移，问此时 \(A,B\) 的凸包是否存在交集。
可以想到，存在交集当且仅当 \(\exists a\in A\text{的凸包}, b\in B\text{的凸包}, b+(dx,dy) = a\)，将其变形，可以得到：
\[\exists a\in A\text{的凸包}, b\in B\text{的凸包}, (dx,dy) = a-b \]转化一下，可以得到这个命题：
\[(dx,dy) \in (A-B)\text{的凸包} \]这里的 \(-B\) 是指将 \(B\) 中的所有坐标取反。
这里直接用闵可夫斯基和求出 \(A-B\) 的凸包，然后判断一下 \((dx,dy)\) 是否在凸包中即可。