这道题目是ROI 2017 Day 1的T3「虎」，是一个交互式几何定位问题。你需要通过查询来确定老虎的位置。

题目理解

问题本质

• 平面上有 n 个固定点（接收器），q 只老虎（需要定位）。
• 每只老虎的位置是固定的，但未知。
• 你可以进行查询：选择不超过 m 个接收器组成一个凸多边形，询问老虎是否在这个多边形内。
• 目标是：对每只老虎，用尽量少的查询找到它所在的空凸多边形（多边形内没有其他接收器，且只有这只老虎）。

约束条件

• 3 ≤ n ≤ 5000
• 1 ≤ q ≤ 10（对于关键子任务）
• 查询次数限制 k = 10000
• 每次查询最多选 m 个点（实际上题目中没说上限，但显然 m ≤ n）

解题思路

核心观察

1. 空凸多边形：定位老虎的空凸多边形必须内部不包含其他接收器，且只包含这只老虎。
2. 单调链结构：代码中使用了一种巧妙的分治+凸壳的方法。

算法解析

代码的主要思路：

1. 预处理

• 将所有接收器按 x 坐标排序（x 相同按 y 排序）。
• 对每个起始位置 i，构建一个特殊凸包 hull[i]：
  • 第一次从左到右扫描（下凸壳）
  • 第二次从右到左扫描（上凸壳）
  • 形成一个逆时针的凸多边形

2. 二分查找

对于每只老虎：

1. 外层二分：找到最大的 id，使得老虎在 hull[id] 内。

   • hull[id] 是由点 s[id], s[id+1], ..., s[n] 构成的凸包。
   • 性质：如果老虎在 hull[i] 内，那么它在所有 hull[j]（j ≤ i）内。
   • 所以二分查找可以快速定位到 id。

2. 内层二分：在 node[id] 中定位具体位置。

   • node[id] 是连接 hull[id] 和 hull[id+1] 的路径点。
   • 通过三角形查询定位具体边。

3. 数据结构

• s[]：排序后的接收器编号
• hull[i]：从点 i 开始的凸包
• node[i]：连接 hull[i] 和 hull[i+1] 的中间结构
• 查询使用：
  • query_convex(id)：查询老虎是否在凸包 hull[id] 内
  • query_triangle(u,v,w)：查询老虎是否在三角形内

查询复杂度

• 外层二分：O(log n) 次查询
• 内层二分：O(log n) 次查询
• 总查询次数：O(log² n) 每只老虎
• 对于 n=5000，大约需要 2 * log₂(5000) ≈ 2*13 = 26 次查询

代码关键点

1. 凸包构建 (build 函数)

void build(int id) {
    // 构建从点id开始的凸包
    // 使用Andrew's Monotone Chain算法变种
}

• 第一遍：下凸壳（从左到右）
• 第二遍：上凸壳（从右到左）
• 形成逆时针凸多边形

2. 路径构建 (node 数组)

// 连接hull[i]和hull[i+1]的路径
while (true) {
    node[i].push_back(hull[i+1][spos]);
    if (hull[i+1][spos] == nxt) break;
    spos = (spos + 1) % hull[i+1].size();
}

3. 定位过程

// 外层二分
int l = 1, r = n-2, best = 0;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (query_convex(mid)) {
        best = mid;
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}

正确性证明

关键性质

1. 单调性：如果老虎在 hull[i] 内，那么它一定在 hull[j]（j < i）内。

   • 因为 hull[j] 包含的点集是 hull[i] 的超集。

2. 空凸性：最终定位的三角形是空的（内部没有其他接收器）。

   • 由凸包和路径的结构保证。

3. 包含性：老虎一定在最终找到的三角形内。

   • 通过两次二分确保了这一点。

实现细节

边界情况处理

if (bl == 0) {
    // 特殊情况：老虎在前三个点形成的区域内
    printf("! 3 %lld %lld %lld\n", s[1], s[2], s[3]);
    continue;
}

内存优化

• 使用 vector 而不是固定数组避免栈溢出
• 只存储必要的凸包和路径

复杂度分析

时间复杂度

1. 预处理：O(n²)（每个起点构建凸包）
2. 每只老虎定位：O(log² n) 次查询
3. 总查询次数：O(q * log² n)

空间复杂度

• O(n²) 存储所有凸包
• 对于 n=5000，这是可以接受的

改进可能

1. 查询优化：可以进一步减少查询次数
2. 内存优化：对于大数据可以增量构建凸包
3. 并行处理：多只老虎可以共享预处理结果

总结

这道题的核心是几何分治+二分：

1. 通过排序建立单调性
2. 构建层级凸包结构
3. 使用二分查找快速定位
4. 利用空凸多边形性质保证正确性

代码巧妙地利用了凸包的性质，通过两次二分将定位问题分解，在查询次数限制内完成了定位任务。