AT_abc251_g Intersection of Polygons Solution
escapist404
·
·
题解
AT_abc251_g Intersection of Polygons Solution
Preface
由于某些 \LaTeX 的原因，本文的公式无法正常查看，建议读者访问博客以获得正常阅读体验。
Statement
逆时针地给定一个有 N 个顶点，第 i 个顶点为 (x_i, y_i) 的凸包 P_0。
再给出 M 个向量 (u_i, v_i) 代表凸包 P_1, P_2, \cdots, P_M，凸包 P_j 有 N 个顶点，第 i 个顶点为 (x_i + u_j, y_i + v_j)。
最后有 Q 组询问，每次给定一个点 (a_i, b_i)，要求判断这个点是否在每一个凸包的内部。
注意凸包的边上也算是它的内部。
保证 3 \le N \le 50，1 \le M, Q \le 2 \cdot {10}^5，-{10}^8 \le x_i, y_i, u_i, v_i, a_i, b_i \le {10}^8。
Solution
考虑某个询问 (a, b)。
注意到 (a, b) 在多边形 P_j 中，当且仅当其被 N 条边“围住”，考虑利用向量的叉积进行判断。具体地：
对于从 (x_i, y_i) 到 (x_{i + 1}, y_{i + 1}) 的向量
\mathbf{f_i}=
\begin{pmatrix}
x_{i + 1} + u_j - (x_i + u_j) \\
y_{i + 1} + v_j - (y_i + v_j)
\end{pmatrix}=
\begin{pmatrix}
x_{i + 1} - x_i \\
y_{i + 1} - y_i
\end{pmatrix}
考虑另一条从 (x_i + u_j, y_i + v_j) 到 (a, b) 的向量
\mathbf{d_i} = \begin{pmatrix}
a - (x_i + v_j) \\
b - (y_i + u_j)
\end{pmatrix}
那么，如果有
\mathbf{f_i} \times \mathbf{d_i} \ge 0
即
\begin{pmatrix}
x_{i + 1} - x_i \\
y_{i + 1} - y_i
\end{pmatrix}
\times
\begin{pmatrix}
a - (x_i + v_j) \\
b - (y_i + u_j)
\end{pmatrix}
\ge 0
记为 (S) 式。
就可以说明点 (a, b) 在 \mathbf{f_i} 方向的左侧，而顶点是逆时针给出的，因此 (a, b) 必定在凸包内部。
向量的叉积
规定
\begin{pmatrix}
a \\
b
\end{pmatrix}
\times
\begin{pmatrix}
c \\
d
\end{pmatrix}
= ad - bc
可以使用右手定则判断叉积的正负。
可参考下图进行理解：
这样朴素地求解是 O\big(Q N M\big) 的。考虑进行优化。
由
\begin{pmatrix}
a - (x_i + v_j) \\
b - (y_i + u_j)
\end{pmatrix}=
\begin{pmatrix}
a \\
b
\end{pmatrix}-
\begin{pmatrix}
x_i + v_j \\
y_i + u_j
\end{pmatrix}
设
\mathbf{g'_{i, j}} =
\begin{pmatrix}
x_i + v_j \\
y_i + u_j
\end{pmatrix}
$$
\begin{pmatrix}
x_{i + 1} - x_i \\
y_{i + 1} - y_i
\end{pmatrix}
\times
\begin{pmatrix}
a \\
b
\end{pmatrix}
\ge
\begin{pmatrix}
x_{i + 1} - x_i \\
y_{i + 1} - y_i
\end{pmatrix}
\times
\begin{pmatrix}
x_i + v_j \\
y_i + u_j
\end{pmatrix}
$$
即
$$
\mathbf{f_i}
\times
\begin{pmatrix}
a \\
b
\end{pmatrix}
\ge
\mathbf{f_i}
\times
\mathbf{g'_{i, j}}
$$
该式对所有 $j$ 成立的充要条件是
$$
\mathbf{f_i}
\times
\begin{pmatrix}
a \\
b
\end{pmatrix}
\ge
\max^M_{\mathbf{j}=1}
\big\lbrace
\mathbf{f_i}
\times
\mathbf{g'_{i, j}}
\big\rbrace = \mathbf{g_i}
$$
这样，我们预处理出 $\mathbf{f_i}$ 和 $\mathbf{g_i}$，在处理单个询问时枚举 $\mathbf i$ 即可。
时间复杂度为 $N + N M + N Q = O\big(N (M + Q)\big)$。
注意 $(x_N, y_N)$ 到 $(x_1, y_1)$ 的向量应当考虑为 $\mathbf{f_N}$。
## Reference
* [判断一个点在直线的哪边 - OI-wiki](https://oi-wiki.org//geometry/2d/#%E5%88%A4%E6%96%AD%E4%B8%80%E4%B8%AA%E7%82%B9%E5%9C%A8%E7%9B%B4%E7%BA%BF%E7%9A%84%E5%93%AA%E8%BE%B9)
* [向量的叉积（叉乘、外积）- OI-wiki](https://oi-wiki.org//math/linear-algebra/product/#%E5%A4%96%E7%A7%AF)
* [Accepted Submission](https://atcoder.jp/contests/abc251/submissions/42103528)
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
class Vector {
public:
LL x, y;
Vector(LL _x, LL _y) {
x = _x, y = _y;
}
};
Vector operator + (const Vector x, const Vector y) {
return Vector(x.x + y.x, x.y + y.y);
}
Vector operator - (const Vector x, const Vector y) {
return Vector(x.x - y.x, x.y - y.y);
}
LL cross(const Vector x, const Vector y) {
return x.x * y.y - x.y * y.x;
}
vector <Vector> p, f;
vector <LL> g;
int n, m, q;
int main() {
ios::sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
LL _x, _y;
cin >> _x >> _y;
Vector tmp(_x, _y);
p.push_back(tmp);
}
p.push_back(p.front());
for(int i = 0; i < n; ++i) {
f.push_back(p[i + 1] - p[i]);
}
for(int i = 0; i < n; ++i) {
g.push_back(-1e18);
}
cin >> m;
for(int i = 1; i <= m; ++i) {
LL _u, _v;
cin >> _u >> _v;
Vector c(_u, _v);
for(int j = 0; j < n; ++j) {
if(cross(f[j], (p[j] + c)) > g[j]) {
g[j] = cross(f[j], (p[j] + c));
}
}
}
cin >> q;
for(int i = 1; i <= q; ++i) {
LL _a, _b;
cin >> _a >> _b;
Vector c(_a, _b);
bool ans = 1;
for(int j = 0; j < n && ans; ++j) {
ans &= (cross(f[j], c) >= g[j]);
}
cout << (ans ? "Yes" : "No") << endl;
}
return 0;
}
```