AT_abc251_g Intersection of Polygons Solution
escapist404
2023-06-11 00:49:53
# AT_abc251_g Intersection of Polygons Solution
## Preface
由于某些 $\LaTeX$ 的原因，本文的公式无法正常查看，建议读者访问[博客](https://www.luogu.com.cn/blog/284754/solution-at-abc251-g)以获得正常阅读体验。
## 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}
$$
$(S)$ 式等价于
$$
\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;
}
```