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} \]\((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
Code
#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;
}
标签:begin,end,times,Vector,pmatrix,mathbf,Intersection,Polygons,abc251
From: https://www.cnblogs.com/escap1st/p/17571716.html