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;
}