CEOI 2018 Triangles 题解

题目分析

这道题要求通过交互方式找出平面上n个点的凸包顶点数，只能通过询问三点方向来判断相对位置。

关键约束：

• 只能使用 is_clockwise 函数判断三点方向
• 最多 10^6 次询问
• n 最大 40000

解题思路

核心观察

1. 增量构造：可以逐步添加点来构建凸包
2. 二分查找：对于新点，可以二分找到它在凸包上的插入位置
3. 方向判断：通过三点方向关系判断点是否在凸包内部

算法设计

代码采用了随机化增量法构建凸包：

主要步骤：

1. 随机打乱：随机点顺序避免最坏情况
2. 初始三角形：用前三个点构建初始凸包
3. 增量插入：对每个新点，二分找到在凸包上的正确位置
4. 维护凸包：删除被新点"覆盖"的旧点

代码详解

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;

int id[40005];
vector<int> p;  // 当前凸包点（逆时针顺序）
int n, m;

// 循环前驱
inline int pre(int x) {
    return !x ? m - 1 : x - 1;
}

// 循环后继  
inline int suf(int x) {
    return x + 1 == m ? 0 : x + 1;
}

// 修改凸包：在边x->(x+1)处插入点k
void mfy(int x, int k) {
    int pr = x, su = x;

    // 向左扩展：删除不再在凸包上的点
    while (is_clockwise(p[pre(pr)], p[pr], k) == 1)
        pr = pre(pr);

    // 向右扩展：删除不再在凸包上的点
    while (is_clockwise(p[suf(su)], p[suf(suf(su))], k) == 1)
        su = suf(su);

    // 插入新点，删除被覆盖的旧点
    if (pr == su) {
        p.insert(p.begin() + pr + 1, k);
    } else {
        pr = suf(pr);
        if (pr <= su) {
            p.erase(p.begin() + pr, p.begin() + su + 1);
            p.insert(p.begin() + pr, k);
        } else {
            // 处理循环情况
            p.erase(p.begin() + pr, p.end());
            p.erase(p.begin(), p.begin() + su + 1);
            p.emplace_back(k);
        }
    }
}

// 插入新点x到凸包
void ins(int x) {
    m = p.size();

    // 检查是否可以插入到首边
    if (is_clockwise(x, p[0], p[1]) == 1)
        return mfy(0, x);

    // 检查是否可以插入到尾边
    if (is_clockwise(x, p[m - 1], p[0]) == 1)
        return mfy(m - 1, x);

    // 二分查找插入位置
    int l = 1, r = m - 2;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (is_clockwise(p[0], p[mid + 1], x) == 1)
            r = mid;
        else
            l = mid + 1;
    }

    // 检查找到的边是否可以插入
    if (is_clockwise(p[l], p[l + 1], x) == 1)
        mfy(l, x);
}

int main() {
    n = get_n();

    // 随机打乱点顺序
    for (int i = 1; i <= n; ++i)
        id[i] = i;
    shuffle(id + 1, id + 1 + n, mt19937(time(0)));

    // 构建初始三角形（确保逆时针顺序）
    if (!is_clockwise(id[1], id[2], id[3]))
        p = {id[1], id[2], id[3]};
    else
        p = {id[1], id[3], id[2]};

    // 增量插入剩余点
    for (int i = 4; i <= n; ++i)
        ins(id[i]);

    give_answer(p.size());
    return 0;
}

算法原理详解

1. 凸包维护

维护的凸包点集 p 按逆时针顺序存储。

2. 点插入逻辑

对于新点 k：

1. 检查首尾边：先检查是否能插入到凸包的首边或尾边
2. 二分查找：否则二分找到点 k 相对于凸包的"可见区域"
3. 范围删除：找到插入位置后，删除被新点覆盖的旧凸包点

3. 方向判断含义

• is_clockwise(a,b,c) == true：点c在向量ab的右侧
• is_clockwise(a,b,c) == false：点c在向量ab的左侧

在逆时针凸包中，内部点都在所有边的左侧。

4. 修改操作

mfy(x, k) 在边 p[x] -> p[x+1] 处插入点 k：

• 向左检查：删除不再在凸包上的点
• 向右检查：删除不再在凸包上的点
• 插入新点，删除被覆盖的区间

复杂度分析

• 时间复杂度：$O(n \log n)$ 每次插入二分 $O(\log n)$，维护 $O(1)$
• 空间复杂度：$O(n)$ 存储凸包点
• 询问次数：$O(n \log n)$，满足 $10^6$ 限制

关键技巧

1. 随机化：避免最坏情况，保证期望复杂度
2. 循环处理：凸包是循环结构，需要特殊处理首尾连接
3. 二分查找：高效定位插入位置
4. 批量删除：一次插入可能删除多个旧点

样例验证

对于样例中的6个点：

1. 随机顺序开始处理
2. 构建初始三角形
3. 逐个插入剩余点
4. 最终凸包包含4个顶点

正确性证明

算法基于凸包的标准增量构造：

• 初始三角形是凸包
• 每次插入维护凸包性质
• 通过方向测试确保点相对位置正确
• 最终得到完整凸包

总结

这道题的解题亮点：

1. 交互策略：在有限询问下解决问题
2. 增量构造：逐步构建最终解
3. 几何直觉：利用方向关系判断点的相对位置
4. 高效实现：通过二分和批量操作优化性能

算法展示了计算几何中凸包构造的经典方法，通过巧妙的交互策略在约束条件下高效解决问题。