problem
给你两个平面凸多边形 \(A,B\)，\(Q\) 次询问，每次询问是一个向量 \(\vec v\)，回答 \(A\) 与 \(B + \vec v\) 是否有交。\(n,Q \leq 10^5\)。
solution
观察闵可夫斯基和（Minkowsky sum）的定义，若将这个运算定义为 \((*) :: [Point] \to [Point] \to [Point]\)，则满足：
\[A * B=\{ a + b | a \in A, b \in B\}.
\]
即两个凸包内所有点两两加起来得到的新的东西，闵可夫斯基证明了 \(A*B\) 也是一个凸包。闵可夫斯基和在凸壳 / 凸函数上，有另外的理解：
\[(A * B)[c] = \max_{a + b =c}\{ A[i] + B[j] \}.
\]
可能有点抽象，就是两个序列的 \((+,\max)\) 卷积。
闵可夫斯基和的结论是 \(A * B\) 的所有边是 \(A,B\) 的边集的和（暴力按一定顺序拼接成新的凸包），或者 \(A * B\) 的差分是 \(A,B\) 各自的差分的归并。实现可以使用归并排序，在 \(O(n)\) 的时间内完成。
回到此题，两个凸包没有交，就是
\[\forall a \in A, b \in B, a \neq b.
\]
加上向量 \(\vec v\) 后变成：
\[\forall a \in A, b \in B, a \neq b + \vec v \implies a - b \neq \vec v.
\]
就是说，如果我们能求出 \(\{ a - b | a \in A, b \in B\}\) 这个集合，那么只需要判断 \(\vec v\) 在不在这个集合中。然而这个集合是闵可夫斯基和的形式，只需要求出 \(A * (-B)\) 就好了。然后判断点是否在凸包内，也是经典问题，只要二分找到这个点大概是哪两条对角线夹着，然后判断是否在那个三角形内。
code
点击查看代码
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <utility>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template<class T> struct dot_t {
T x, y;
dot_t operator+(const dot_t& b) const { return {x + b.x, y + b.y}; }
dot_t operator-(const dot_t& b) const { return {x - b.x, y - b.y}; }
dot_t operator*(const T& k) const { return {x * k, y * k}; }
T operator*(const dot_t& b) const { return x * b.x + y * b.y; }
T friend dist(const dot_t& a) { return a * a; }
T friend cross(const dot_t& a, const dot_t& b) {
return a.x * b.y - a.y * b.x;
}
bool friend cmp(const dot_t& a, const dot_t& b) {
return cross(a, b) ? cross(a, b) > 0 : dist(a) < dist(b);
}
bool friend operator<(const dot_t& a,const dot_t& b) {
return a.x != b.x ? a.x < b.x : a.y < b.y;
}
};
typedef dot_t<LL> dot;
vector<dot> convexHull(vector<dot> a) {
static dot stk[1 << 18];
dot cen = *min_element(a.begin(), a.end());
sort(a.begin(), a.end(),
[&](const dot& a,const dot& b) { return cmp(a - cen, b - cen); });
int top = 0;
for (dot v: a){
while (top >= 2 && cross(stk[top - 1] - stk[top], v - stk[top]) > 0)
top--;
stk[++top] = v;
}
return vector<dot>(stk + 1, stk + top + 1);
}
vector<dot> minkowski(const vector<dot>& a, const vector<dot>& b) {
vector<dot> c = {a[0] + b[0]};
static dot sa[1 << 18], sb[1 << 18];
int n = a.size(), m = b.size();
for (int i = 0; i < n; i++)
sa[i] = a[(i + 1) % n] - a[i];
for (int i = 0; i < m; i++)
sb[i] = b[(i + 1) % m] - b[i];
int i = 0, j = 0;
for (int k = 1; k < n + m; k++){
if (i < n && (j >= m || cmp(sa[i], sb[j])))
c.push_back(c.back() + sa[i++]);
else
c.push_back(c.back() + sb[j++]);
}
return c;
}
bool checkIn(const vector<dot>& a, const dot& v) {
dot cen = a[0];
if (cmp(a.back() - cen, v - cen))
return 0;
//if (cmp(v - cen, a[1] - cen)) return 0;
if (cross(v - cen, a[1] - cen) ? cross(v - cen, a[1] - cen) > 0
: dist(v - cen) > dist(a[1] - cen))
return 0;
auto p =
lower_bound(a.begin() + 1, a.end(), v, [&](const dot& a,const dot& b) {
return cmp(a - cen, b - cen);
});
return cross(*prev(p) - *p, v - *p) <= 0;;
}
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
vector<dot> a(n), b(m);
for (dot& v: a)
scanf("%lld%lld", &v.x, &v.y);
for (dot& v: b)
scanf("%lld%lld", &v.x, &v.y), v.x = -v.x, v.y = -v.y;
vector<dot> c = minkowski(convexHull(a), convexHull(b));
for (dot v: c)
debug("(%lld, %lld)\n", v.x, v.y);
while (q--) {
dot v;
scanf("%lld%lld", &v.x, &v.y);
printf("%d\n",checkIn(c, v));
}
return 0;
}