凸包 - Arca's Blog

凸包

动态凸包（上下凸壳法）

我们动态地维护凸包的上凸壳 $U$ 和下凸壳 $L$ ，同时为了避免多余的讨论，我们让凸包最左侧的点 $p_1$ 和最右侧的点 $p_m$ 同时出现在 $U,L$ 里.

我们考虑怎么维护下凸壳（上凸壳同理）。假设点在下凸壳的下方（即凸包外部），如图所示，我们在 $A\sim H$ 下凸壳上加入点 $I$

我们可以看到，为了维护凸包的性质，需要删除一些点。

以 $I$ 为起点向右侧看去， $I,E,F,G,H$ 这五个点也应该组成凸壳。所以，考察 $I,E,F$ ，则 $E$ 不在凸包上，删去；然后考察 $I,F,G$ 发现他们满足凸包的性质，于是停止，因为 $F,G,H$ 在旧凸包上，故一定满足凸包性质。
同理，以 $I$ 为起点向左侧看去， $I,A,B,C,D$ 这五个点也应该组成凸壳。所以考察 $I,C,D$ 后发现 $D$ 应当被删去；然后考察 $I,C,B$ 他们满足凸包的性质，于是停止。

所以， $I$ 的加入需要删除 $D,E$ 两点。总结一下这个流程，为了维护凸包的性质，我们首先找出 $D,E$ 两点使得 $D,E$ 把 $I$ 夹在中间，然后，分别向左、向右不断删除不在新凸包上的点，直到满足凸包的性质。

那我们该怎么判断 $I$ 如果凸包内部呢？实际上，如果 $I$ 在凸包内部，那么从 $I$ 出发向左或者向右都会满足凸包的性质，也就是说，不会删除任何点。我们可以利用这一个结论简化我们的代码。

此外，如果 $I$ 是新点集里最左或者最右的点，那么无论如何都一定会在新凸包上。

动态凸包

例题代码，可以算是模板题：Codeforces 70D

由于这里边界条件判断用的是 != .end(), != .begin()，所以这份代码并不需要预先读入三个点进行凸包的初始化，可以直接插入。

#include <bits/stdc++.h>
using ll = long long;

struct point {
    ll x, y;
    bool operator<(point rhs) const { return x != rhs.x ? x < rhs.x : y < rhs.y; }
    ll cross(point rhs) const { return x * rhs.y - y * rhs.x; }
    point operator-(point rhs) const { return {x - rhs.x, y - rhs.y}; }
    point operator+(point rhs) const { return {x + rhs.x, y + rhs.y}; }
    bool operator==(point rhs) const { return x == rhs.x && y == rhs.y; }
};

class DynConvex {
    std::set<point> lower, upper; // 上下凸壳
    void _insert_lower(point p) {
        auto position = lower.lower_bound(p);
        std::vector<point> trash;

        if (position != lower.end()) {
            auto it = position;
            if (it != lower.end()) {
                auto itt = std::next(it);
                while (it != lower.end() && itt != lower.end() && (*it - p).cross(*itt - p) <= 0) {
                    trash.push_back(*it);
                    it++, itt++;
                }
            }
        }

        if (position != lower.begin()) {
            auto it = std::prev(position);
            if (it != lower.begin()) {
                auto itt = std::prev(it);

                while ((*it - *itt).cross(p - *itt) <= 0) {
                    trash.push_back(*it);
                    if (itt == lower.begin()) break;
                    it--, itt--;
                }
            }
        }

        if (position == lower.begin() || position == lower.end()) lower.insert(p);
        else {
            auto pv = std::prev(position), nx = position;
            if ((p - *pv).cross(p - *nx) <= 0) lower.insert(p);
        }
        for (auto x : trash) lower.erase(x);
    }
    void _insert_upper(point p) {
        auto position = upper.lower_bound(p);
        std::vector<point> trash;

        if (position != upper.end()) {
            auto it = position;
            if (it != upper.end()) {
                auto itt = std::next(it);
                while (true) {
                    if (it == upper.end() || itt == upper.end()) break;
                    if ((*it - *itt).cross(p - *itt) > 0) break;
                    trash.push_back(*it);
                    it++, itt++;
                }
            }
        }

        if (position != upper.begin()) {
            auto it = std::prev(position);
            if (it != upper.begin()) {
                auto itt = std::prev(it);

                while ((*it - p).cross(*itt - p) <= 0) {
                    trash.push_back(*it);
                    if (itt == upper.begin()) break;
                    it--, itt--;
                }
            }
        }

        if (position == upper.begin() || position == upper.end()) upper.insert(p);
        else {
            auto pv = std::prev(position), nx = position;
            if ((p - *pv).cross(p - *nx) >= 0) upper.insert(p);
        }
        for (auto x : trash) upper.erase(x);
    }

  public:
    void add(point p) {
        _insert_lower(p);
        _insert_upper(p);
    }

    bool consult(point p) {
        auto lp = lower.lower_bound(p);
        if (*lp == p) return true;
        else if (lp == lower.end() || lp == lower.begin()) return false;

        auto up = upper.lower_bound(p);
        if (*up == p) return true;
        else if (up == upper.end() || up == upper.begin()) return false;

        auto plp = std::prev(lp), pup = std::prev(up);
        if ((p - *plp).cross(p - *lp) >= 0 && (p - *pup).cross(p - *up) <= 0) return true;
        else return false;
    }
} hull;

int q, op;
ll x, y;

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);

    std::cin >> q;
    while (q--) {
        std::cin >> op >> x >> y;
        if (op == 1) hull.add({x, y});
        else std::cout << (hull.consult({x, y}) ? "YES" : "NO") << "\n";
    }
}

凸包上的经典算法

点是否在凸包内部

方法一：上下凸壳判定法（适用 Andrew 算法）

如果我们已知上凸壳和下凸壳，那么点在凸包内部的充要条件是点既在下凸壳的上方、又在上凸壳的下方.

这里，我们假定上下凸壳的起点、终点的两个点是相同的。

我们如何判断点 $P$ 是否在下凸壳的上方呢？我们按横坐标对下凸壳排序，找出两个点 $A,B$ 使得 $A$ 在 $P$ 的左侧， $B$ 在其右侧。这一步可以通过二分找到。

如果 $A$ 或者 $B$ 不存在，那么就说明 $P$ 一定在凸包的外部。否则，判断叉积 $\vec{PA}\times \vec{PB}$ ，若 $\ge 0$ 说明在凸壳上或者在凸壳上方，若 $\lt 0$ 则说明在凸壳下方。

上凸壳也是同理，先二分再判断叉积。时间复杂度 $O(\log n)$ .

上下凸壳判定法

这里，*lp == p 和 *up == p 还额外判定了在凸壳角点的情况。这是必要的，因为当点在凸包外部左侧，或者恰好为凸包上最左侧的点时，lower_bound() 都会找到 $\texttt{lower.begin()}$ ，从而被 $\texttt{else if}$ 过滤掉。因此，我们需要手动排除恰好为凸包最左侧点时的情况.

bool consult(point p) {
    auto lp = lower.lower_bound(p);
    if (*lp == p) return true;
    else if (lp == lower.end() || lp == lower.begin()) return false;

    auto up = upper.lower_bound(p);
    if (*up == p) return true;
    else if (up == upper.end() || up == upper.begin()) return false;

    auto plp = std::prev(lp), pup = std::prev(up);
    if ((p - *plp).cross(p - *lp) >= 0 && (p - *pup).cross(p - *up) <= 0) return true;
    else return false;
}

方法二：二分三角形法（适用 Graham 算法）

假设我们已知凸包上的所有点（并且按顺时针/逆时针排列好了），我们可以使用二分法判断点是否在凸包的内部。我们固定凸包上的一个点向其他顶点发射线，那么可以切分出 $n-2$ 个三角形。

假设我们现在判断点 $P$ 是否在凸包内部，这里我们选择 $C$ 为基点。我们先使用二分找出 $\vec{CP}$ 被哪两条射线夹住，然后再判断点 $P$ 是否在这个三角形内部。

二分的话，可以判断叉积是否 $\ge 0$ ，判断是否在三角形的内部可以判断 $\vec{PC_i}\times \vec{PC_{i+1}}$ 的符号搞定。