插入均摊 O(log n) 的动态凸包，极角排序

· · 题解

建凸包，除了 Andrew 算法还有 Graham 扫描法。然而有人认为“极角排序”丢精度、效率低，这里我给一个不需要 atan2 的极角排序。

怎么“极角排序”

为了方便，我们定义从原点沿 y 轴负半轴方向的向量角度最小，逆时针旋转越来越大。

例如上图 a 的角度小于 b 的角度。

一个朴素的想法：判断两个向量 a 的角度是否小于 b 的角度，可以通过 a 的斜率与 b 的斜率比较。但是向量在 y 轴上时没法计算斜率，我们需要一些特判。

  1. 如果 a, b 在 y 轴右侧，a 的角度比 b 的角度小且当 a 的斜率小于 b 的斜率。
  2. 如果 a, b 在 y 轴左侧或其中一个在 y 轴上另一个在 y 轴左侧，将它们绕原点旋转 180^{\circ} 二者角度关系不变，变成了第一种情况。
  3. 如果 a, b 在 y 轴两侧，哪个在右侧哪个角度小。
  4. 当 a, b 在 y 轴上时，谁朝下谁角度小。二者都朝下，角度相同。
  5. 当 a 在 y 轴上，b 在 y 轴右侧（从情况 2 转换来的），如果 a 朝下那么 a 角度小，如果 a 朝上 a 角度大。b 在 y 轴上时类似。

原点不会出现在凸包的边缘上，不需要考虑原点的角度。

bool operator<(vec a, vec b) {
    if (a.x == 0 && b.x == 0) {
        if (signbit(a.y) == signbit(b.y)) { // 4
            return false;
        }
        return a.y < 0;
    }
    if (a.x <= 0 && b.x <= 0) { // 2
        return -a < -b;
    }
    if ((a.x == 0 && a.y < 0) || (b.x == 0 && b.y > 0)) { // 5
        return true;
    }
    if ((a.x == 0 && a.y > 0) || (b.x == 0 && b.y < 0)) { // 5
        return false;
    }
    if (signbit(a.x) != signbit(b.x)) { // 3
        return a.x > b.x;
    }
    return (long long) a.y * b.x < (long long) b.y * a.x; // 1
}

剩下的部分

我们把给我们所有的点的坐标都乘上 3 。由一开始的三个点，计算出这三个点围成的三角形的重心（因为坐标都乘上 3 所以重心的坐标必为整数），并将所有点一起平移，使得重心落在原点上。这样处理方便我们比较角度。

用平衡树维护凸包边缘上的点（向量），按极角排序。

考虑怎么做询问。记给我们的向量为 b ，在凸包边缘上角度小于 b 且最大的向量为 a （b 的前驱），角度大于等于 b 且最小的向量为 c （b 的后继）。判断 b 是否在凸包上（内部和边缘），只需要判断 b 是否在 ac 的左侧或边缘，即 \overrightarrow{ac} \times \overrightarrow{ab} \ge 0 。

// 这里实现的是 "b" 是不是在凸包外。hull 是 std::set 。prev 不是 std::prev ，是我自己写的 prev 。
// prev(hull.begin()) == std::prev(hull.end()) 。
// 同理下面 insert 中的 next 也不是 std::next ，是我自己写的 next 。
bool outHull(vec b) {
    auto it = hull.lower_bound(b);
    if (it == hull.end()) {
        it = hull.begin();
    }
    auto c = *it, a = *prev(it);
    return cross({a, c}, {a, b}) < 0;
}

考虑怎么做插入。首先判断给我们的点 p 是不是在凸包上（内部和边缘）。如果在凸包上那么就不用插入了。然后把 p 插入到平衡树中。如左上图，逆时针，给 p 周围的向量起个名。 p 插入后 d, c, p 是凹的，即 \overrightarrow{pc} \times \overrightarrow{cd} \le 0 ，删除 c 。删完后可能还是凹的，重复这个过程。同理 p, b, a 是凹的，即 \overrightarrow{pb} \times \overrightarrow{ba} \ge 0 ，把 b 删掉，如果还是凹的就重复这个过程。

void insert(vec v) {
    hull.erase(v); // 方向相同的向量会被判为相等
    auto it = hull.insert(v).first;
    while (cross({*it, *next(it)}, {*next(it), *next(it, 2)}) <= 0) {
        hull.erase(*next(it));
    }
    while (cross({*it, *prev(it)}, {*prev(it), *prev(it, 2)}) >= 0) {
        hull.erase(*prev(it));
    }
}

分析下时间复杂度，平衡树选用红黑树，查找 \Theta(\log n) ，插入 O(1) ，删除 O(1) 。对于询问，相当于两次查找，时间复杂度是 \Theta(\log n) 。对于插入，查找 p 需要插入的位置 \Theta(\log n) ，由于一个点只能删除一次，均摊到每次操作 1 就是 O(1) 的，所以时间复杂度是均摊 \Theta(\log n) 。

题外话

注意到插入的时间复杂度是均摊 \Theta(\log n) ，有没有什么严格 \Theta(\log n) 的做法？答案是有的。《COMPUTATIONAL GEOMETRY AN INTRODUCTION》中 3.3.6 节提到了这一做法，3.3.7 节提到了有插入、删除维护动态凸包的 \Theta(\log^2 n) 做法。各位有兴趣可以去看看，讲得挺好。

不难想出本题还有一个询问 \Theta(\log n) ，插入 \Theta(\sqrt{n}) 的做法，基于块状链表。不好说实现出来有没有我上文介绍了一大顿类似 Graham 扫描法的解法快。说到效率，我开了 Ofast 和快读后就拿到 codeforces 上的最优解了。测评记录

有问题可以在评论区中问我。如果发现了我的题解有错误麻烦各位指出，谢谢。