原题：POJ 3608 Bridge Across Islands（POJ 评测机太老仅 C++98，强烈推荐 vjudge 上的镜像 OpenJ_Bailian-3851）。本题是两凸多边形最近距离的旋转卡壳模板题，但有一个反直觉的「单调推进准则」选择 —— 第一版贪心在 OJ 上 TLE，调试改 cross 单调推进后又 WA，最终发现单次调用对偶覆盖不完整，必须 (A, B) 和 (B, A) 各跑一次。

题目大意

太平洋中央有一个王国，领土由两座岛屿组成，被洋流冲成两个凸多边形。国王要造一座桥连两岛，问两岛边界的最小距离是多少。

输入

多组测试用例。每组先给两整数 $N$ 和 $M$ ( $3 \le N, M \le 10000$ )，接下来 $N$ 行各给一对坐标描述第一个凸多边形的一个顶点（已按某种顺序给出，CW 或 CCW），再接 $M$ 行给第二个凸多边形顶点。坐标 $\in [-10000, 10000]$ 。

一行 $N = M = 0$ 表示输入结束。

输出

每组输出最小距离，误差 $\le 10^{-3}$ 。

样例

1
2
3
4
5
6
7
8
9
10

4 4
0.00000 0.00000
0.00000 1.00000
1.00000 1.00000
1.00000 0.00000
2.00000 0.00000
2.00000 1.00000
3.00000 1.00000
3.00000 0.00000
0 0

输出：

1

1.00000

思路讲解

一句话

两凸多边形最近距离 = 旋转卡壳 + facing 弧双指针 $O(N + M)$ ；推进准则用「cross(a, b') 角度差」、不要用「dis2 < dis1 顶点-边距离单峰」（贪心在背面弧会卡住）；最终结果必须 (A, B) 和 (B, A) 各调一次取 $\min$ 才覆盖完整。

把最近距离归并到「顶点 → 线段」

两个不相交的凸多边形之间，最小距离的实现位置只有三种：

关键不变量：枚举所有 $(顶点,\ \mathrm{对面边})$ 对，算点-线段距离取 $\min$ ，三种情形一网打尽。

facing 弧 + 单调推进

固定 $A$ 上一个顶点 $p$ ，凸性下 $B$ 上「真正可能成为离 $p$ 最近的那条边」有且仅有一条 —— 称它为 $p$ 的 facing edge。形象点：从 $p$ 看过去， $B$ 朝向 $p$ 那半弧上正对 $p$ 的那条边，其它边要么被它挡住、要么转到背面去了。

把 $p$ 沿 $A$ 走 CCW 一圈，那条 facing 边在 $B$ 上的位置是**「短程单调、长程往返」**：

• 短程（ $p$ 走在 $A$ 朝 $B$ 那半弧上）：facing 边在 $B$ 上 单调推进（不回退）

• 长程（ $p$ 越过 $A$ 的背面弧）： $B$ 没有新边可选，facing 边只能沿同一段 facing 弧 退回来

• 整圈轨迹 = 「推过去 → 退回来」 = 往返

算法直接好处：两个指针不需要走完一整圈，各自只走完自己的 facing 弧就够了，总步数 $\le N + M$ 。

初始 facing pair：A 最低 + B 最高

按代码取：

• $\texttt{eA}$ = $A$ 上 $y$ 最小的点的下标

• $\texttt{eB}$ = $B$ 上 $y$ 最大的点的下标

几何上 $\texttt{eA}$ 看上去就是 $\texttt{eB}$ 、 $\texttt{eB}$ 看下去就是 $\texttt{eA}$ —— 这一对是初始 facing pair，也是 $A$ / $B$ 各自 facing 弧的一个端点。

不过这个初始只在「 $B$ 整体在 $A$ 上方」时直观对齐；其它分布下（ $A$ 在右、 $B$ 在左之类）yMnA + yMxB 不一定是真 facing pair。没关系 —— 推进准则用 cross 角度差驱动后，初始位置不正确也能在 $O(N + M)$ 步内追上正确的对踵 pair，所以这个朴素初始化就够了。

cross(a, b') 推进准则（核心）

设：

• $\vec{a} = A_{i+1} - A_i$ ： $A$ 在 $A_i$ 的 CCW 出边方向

• $\vec{b}' = B_j - B_{j+1}$ ： $B$ 在 $B_j$ 的 CCW 出边 反向（因为 $B$ 的 facing 弧逆 $B$ 的 CCW 序前进）

推进准则：

$$\mathrm{cross}(\vec{a},\ \vec{b}') \quad \begin{cases} > 0 & \Rightarrow\ \mathtt{++i}\ \text{（推进 A）} \\ < 0 & \Rightarrow\ \mathtt{++j}\ \text{（推进 B）} \\ = 0 & \text{两个都试一下取 min} \end{cases}$$

几何意义：初始 facing pair 处 $\vec{a}$ 和 $\vec{b}'$ 都大约朝 $+x$ ，几乎平行同向；两者沿各自多边形 CCW 推进时都向 CCW 方向旋转（凸性）。 $\mathrm{cross}(\vec{a},\ \vec{b}')$ 衡量两者角度差：

• $> 0$ ： $\vec{b}'$ 在 $\vec{a}$ 的 CCW 一侧 $\Rightarrow$ $\vec{a}$ 角度落后 $\Rightarrow$ 让 $A$ 推一步追上

• $< 0$ ：反之，让 $B$ 推一步

为什么这样不会 TLE：每步刚好推一个指针、各自只能 forward。 $i$ 走完 $A$ 一圈、 $j$ 走完 $B$ 一圈就停，总步数 $\le N + M$ 。背面弧问题自动消失 —— cross 一直按角度差驱动，根本不依赖「dis 谁更小」这种局部贪心。

为什么必须 (A, B) + (B, A) 各调一次

单次 cal_min_dis_two_convex(A, B) 只覆盖**「 $A$ 顶点 → $B$ 边」**这组对偶配置 —— 也就是「枚举 $A$ 上每个顶点，找 $B$ 上对应的 facing 边」。

但反对称几何里答案可能取在另一边：细长 $A$ 戳向粗 $B$ 的边中间， $A$ 的端点垂足落在 $B$ 的边内部 —— 这种「 $A$ 顶点 - $B$ 边」抓得到；反过来「 $B$ 顶点 - $A$ 边」抓不到。

解决：把同一份代码以 (B, A) 参数顺序再跑一遍，补上反向对偶，最后两次取 $\min$ ：

`c++

DB ans = INFINITY;

ans = min(ans, cal_min_dis_two_convex(A, B));

ans = min(ans, cal_min_dis_two_convex(B, A));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

漏一次会在 stress test 第 24 个 seed 翻车（**已实测**，反例见 `counterexample_seed24.html` 附件，期望 $62.29$ 实测 $63.7$ ）。

## 📎 动画与源码

- $\vec{a}$ / $\vec{b}'$ 向量 + `cross` 推进逐步演示：`cross_product_demo.html`（见附件）
- 单次调用对偶不完整反例：`counterexample_one_call_only.html`、`counterexample_seed24.html`

# AC 代码

[**AC 提交链接（vjudge OpenJ\_Bailian-3851）**](https://vjudge.net/solution/69793877)

核心函数：

// 两凸多边形最近距离（旋转卡壳, O(n + m)）

// 单次调用只覆盖「A 边 → B 顶点」配置，

// 调用方需以 (A, B) 和 (B, A) 各调一次取 min。

template

DB cal_min_dis_two_convex(vector<Point> A, vector<Point> B) {

reorder_polygon(A);

reorder_polygon(B);

ll yMnA = min_element(all(A), [](const Point<T> &a, const Point<T> &b) {

    return a.y < b.y;

}) - A.begin();

ll yMxB = max_element(all(B), [](const Point<T> &a, const Point<T> &b) {

    return a.y < b.y;

}) - B.begin();

DB ans = INFINITY;

ll eA = yMnA, eB = yMxB;

for (int _ = 0; _ < SZ(A) + SZ(B); ++_) {

    auto check = [&]() {

        auto vecA = A[(eA + 1) % SZ(A)] - A[eA];

        auto vecB = B[(eB + 1) % SZ(B)] - B[eB];

        return cross(vecA, vecB) > 0;

    };

    while (check()) ++eB, eB %= SZ(B);

    ans = min(ans, distanceSS(Line(A[(eA + 1) % SZ(A)], A[eA]),

                              Line(B[(eB + 1) % SZ(B)], B[eB])));

    eA = (eA + 1) % SZ(A);

}

return ans;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

完整源码（含几何模板、读入、Solve 框架）：

<details>
<summary>展开完整 C++ 源码（Bridge_Across_Islands.cpp）</summary>

完整源码 ~840 行较长，含整套几何模板（`Point` / `Line` / `cross` / `distanceSS` / `reorder_polygon` 等）+ `cal_min_dis_two_convex` + 多组数据 main。直接下载页面末尾附件 `Bridge_Across_Islands.cpp.txt`（去掉 `.txt` 后缀即为 `.cpp`）。

</details>

# 心路历程（TLE → WA → AC）

1. **第一版 TLE**：用「`dis2 < dis1` 顶点-边距离贪心」推进 —— 在 $A$ 朝 $B$ 那半弧上确实单调，但当 $i$ 越过 $A$ 的背面弧后单调性破裂， $j$ 想往回走但只能 forward，**陷在 $B$ 上转圈**，OJ 测出 TLE。
2. **第二版 WA**：换成 `cross(a, b')` 角度判定，单次 `cal_min_dis_two_convex(A, B)` 调用 —— 本地 cyaron stress 用近圆形测 5000 case 全过、提交 OJ WA。`cyaron-stress` skill 警告过：**cyaron `Polygon.convex_hull` 默认近圆形是对拍盲区**，必须主动用 ellipse / spiked / heart / lemon 等曲率非均匀形状才能触发反例。换成椭圆 + spike 形状后，stress seed 24 立刻给出 `yMnA + yMxB` 配对失效的反例（见附件 `counterexample_seed24.html`）。
3. **第三版 AC**：加上 `(B, A)` 反向调用取 $\min$ 补对偶。

\textcolor{red}{**收获心法**}：

- 旋转卡壳推进准则用 **`cross` 角度差** 而不是 **dis 单峰**。「dis 单峰」是教材级 fact 但只在曲率均匀分布下成立。
- 单次调用对偶不完整 —— 看 mentor.tex 里 me/mentor 第 3 步对话录有详细推导，需要 `(A, B)` + `(B, A)` 反向。
- 对拍**必须**用非均匀曲率形状（椭圆 / spike / heart / lemon）破盲区；cyaron `Polygon.convex_hull` 默认值就是盲区本身。

# 附件

Bridge_Across_Islands_html_demos.zip

mentor.tex 编译产物 PDF —— me/mentor 5 步推导对话录（题面 / 三类特征对 / facing 弧 / 旋转卡壳骨架 / cross 推进准则）

Bridge_Across_Islands.cpp.txt

题目大意

原题：CF Round 1093 Div2 D2 - Unique Values (Hard version)（rating 1900）

交互题。有一个长度 $2n+1$ 的隐藏数组 $a$ ，元素值在 $[1, n]$ 之间；其中有且仅有一个值出现 3 次，其余每个值都恰好出现 2 次。要求找出那个出现 3 次的值的三个下标。

每次询问可以选一个下标子集 $S$ ，judge 会返回 $\{a_i : i \in S\}$ 这个多重集里恰好出现一次的值的个数（即把一对一对的去掉以后还剩几种）。

Easy version: $\le 50$ 次询问。Hard version（本题）： $\le 33$ 次询问。 $n \le 1000$ 。

思路讲解

一句话

设那个特殊值（出现 3 次的）为 $T$ ，三个位置 $p_1 < p_2 < p_3$ 。33 次预算 = 3 段二分 × 11 次——每段用 bit-trick 在长度 $\le 2n+1 \le 2001$ 的范围里锁一个位置， $\lceil \log_2 2001 \rceil = 11$ 。三段分别独立设计一个关于 $k$ 单调的奇偶谓词，bit-trick 收敛。

核心 trick：贡献奇偶表

对任一询问集合 $S$ ，记 $\text{len} = |S|$ ， $\text{res}$ 为 judge 返回值。每个值 $v$ 对 $\text{len} - \text{res}$ 的贡献只取决于它在 $S$ 中的 count：

关键不变量：只有 count = 3 那档贡献奇数。本题里能让某个值 count = 3 的，只有那个出现 3 次的特殊值 $T$ 。所以 $(\text{len} - \text{res}) \bmod 2 = 1 \iff T \text{ 在 } S \text{ 里凑齐 } 3 \text{ 个 position}$ 。

其他值（出现 2 次的 double）count $\le 2$ ，贡献全偶，自动从奇偶位上消失——这就是奇偶谓词的威力，doubles 不来添乱。

第 1 段：找 $p_3$

询问 $S_k = [1..k]$ 。 $T$ 在 $S_k$ 里 count = 3 当且仅当 $k \ge p_3$ （三个位置全进来）。

$(k - \text{res}) \bmod 2 = 0 \iff k < p_3$

谓词在 $[0, p_3 - 1]$ 真， $[p_3, N]$ 假。bit-trick 从 $k = 0$ 起按 $2^i$ 加位，找最大的真 $k$ = $p_3 - 1$ ，加 1 即 $p_3$ 。

1
2
3
4
5
6
7
8

ll pos3 = 0;
for (int i = __lg(N); i >= 0; --i) {
    ll k = pos3 + (1ll << i);
    if (k > N) continue;
    ll res = query(1, k);
    if ((k - res) % 2 == 0) pos3 = k;
}
pos3++;

第 2 段：找 $p_1$

知道 $p_3$ 后，询问 $S_k = [k..p_3]$ （后缀）。 $T$ 在 $S_k$ 里 count = 3 当且仅当 $k \le p_1$ （三个位置都在 $[k..p_3]$ 里）。

$(\text{len} - \text{res}) \bmod 2 = 0 \iff k > p_1$

谓词在 $[p_1+1, p_3]$ 真， $[1, p_1]$ 假。bit-trick 从 $k = p_3$ 起降序减位，找最小的真 $k$ = $p_1 + 1$ ，减 1 即 $p_1$ 。

1
2
3
4
5
6
7
8
9

ll pos1 = pos3;
for (int i = __lg(pos3); i >= 0; --i) {
    ll k = pos1 - (1ll << i);   // ← 用当前 pos1，不是 pos3
    if (k < 1) continue;
    ll res = query(k, pos3);
    ll len = pos3 - k + 1;
    if ((len - res) % 2 == 0) pos1 = k;
}
pos1--;

第 3 段：找 $p_2$ （最绕的一段）

$p_1, p_3$ 已知，找 $p_2 \in (p_1, p_3)$ 。这一段最容易写错——不要用「query $[1..k] \setminus \{p_1, p_3\}$ 看 res 是否为 0」这种谓词，那个不单调。

正确设计：让 $T$ 在询问集合里的 count 在 $k$ 跨过 $p_2$ 时从 2 跳到 3（正好覆盖贡献表里的奇偶分界点）。

$S_k = \{p_3\} \cup [p_1..k], \quad k \in [p_1, p_3 - 1]$

T 在 $S_k$ 里： $p_1$ 必入（在 $[p_1..k]$ 里）， $p_3$ 必入（显式塞）， $p_2$ 当且仅当 $k \ge p_2$ 时入。

谓词 $\iff k < p_2$ ，bit-trick 从 $k = p_1$ 起加位，找最大真 $k$ = $p_2 - 1$ ，加 1 即 $p_2$ 。

1
2
3
4
5
6
7
8

ll pos2 = pos1;
for (int i = __lg(pos3 - pos1); i >= 0; --i) {
    ll to = pos2 + (1ll << i);
    if (to >= pos3) continue;
    auto [len, res] = query(pos1, to, pos1, pos3);   // [pos1..to] ∪ {pos1, pos3}
    if ((len - res) % 2 == 0) pos2 = to;
}
pos2++;

询问数核账

合计 $\le 33$ ，正好卡到题目限制。Easy version 给 50 次相对宽松，Hard 这 33 次每段都不能浪费一次询问——所以三个 bit-trick 必须用 continue 越界保护省下不必要的查询。

AC 代码

AC 提交链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define SZ(a) ((long long) a.size())

using namespace std;
using ll = long long;

ll lT, testcase;

ll query(const vector<ll> &posLs) {
    cout << "? " << SZ(posLs) << " ";
    for (auto p: posLs) cout << p << " ";
    cout << endl;
    ll res;
    cin >> res;
    return res;
}

ll query(ll l, ll r) {
    vector<ll> posLs;
    for (int i = l; i <= r; ++i) posLs.push_back(i);
    return query(posLs);
}

pair<ll, ll> query(ll l, ll r, ll pos1, ll pos3) {
    vector<ll> posLs;
    set<ll> st = {pos1, pos3};
    for (int i = l; i <= r; ++i) st.insert(i);
    posLs.reserve(SZ(st));
    for (auto p: st) posLs.push_back(p);
    return {SZ(posLs), query(posLs)};
}

void Solve() {
    ll N;
    cin >> N;
    N = 2 * N + 1;

    // 第 1 段: 找 p3
    ll pos3 = 0;
    for (int i = __lg(N); i >= 0; --i) {
        ll k = pos3 + (1ll << i);
        if (k > N) continue;
        ll res = query(1, k);
        if ((k - res) % 2 == 0) pos3 = k;
    }
    pos3++;

    // 第 2 段: 找 p1
    ll pos1 = pos3;
    for (int i = __lg(pos3); i >= 0; --i) {
        ll k = pos1 - (1ll << i);
        if (k < 1) continue;
        ll res = query(k, pos3);
        ll len = pos3 - k + 1;
        if ((len - res) % 2 == 0) pos1 = k;
    }
    pos1--;

    // 第 3 段: 找 p2 (强制塞 {p1, p3} 当 baseline)
    ll pos2 = pos1;
    for (int i = __lg(pos3 - pos1); i >= 0; --i) {
        ll to = pos2 + (1ll << i);
        if (to >= pos3) continue;
        auto [len, res] = query(pos1, to, pos1, pos3);
        if ((len - res) % 2 == 0) pos2 = to;
    }
    pos2++;

    cout << "! " << pos1 << " " << pos2 << " " << pos3 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase) Solve();
    return 0;
}

心路历程（WA → MLE → AC，被 D2 教做人的 4 个小时）

这道题头一次过 D1（Easy 50 次询问）那版还挺顺，三段二分各用 17 次差不多卡进去就完了。到 D2 把预算压到 33 次才开始遭罪——核心不是"次数压紧"这件事，而是 $p_2$ 那段我第一版完全写歪了思路，后面几次提交几乎都是在为最初这个错误的设计买单。

❌ 第一版：用 !res 当谓词，谓词根本不单调

第一版的想法是「query $[1..k] \setminus \{p_1, p_3\}$ ，看 res 是不是 0」。直觉是「subset 里所有值都成对了 = res = 0 = 还没碰到 $p_2$ 」，然后 bit-trick 找最大的 res = 0 的 $k$ 。

第一次提交：WA on test 1。看了一会才发现一个特别傻的低级错误：

1
2

plus(pos2, 1);   // 这行返回值被丢了！
cout << "! " << pos1 << " " << pos2 << " " << pos3 << endl;

plus 是个按值收 pos2 的纯函数返回新值，我没赋值回来。pos2 全程是 0，输出 ! 1 0 3 直接非法。改成 pos2 = plus(pos2, 1)。

❌ 修了 line 179 后才发现：!res 这个谓词本身就不单调

修完那个赋值，跑反例 $a = [1, 2, 3, 2, 1, 3, 1]$ （ $T=1$ ， $p_2 = 5$ ）发现：

res = 0 只在 $k = 0$ 出现一次，bit-trick 完全收敛不到 $p_2 - 1$ 。res = 0 要求 (a) $p_2 > k$ 且 (b) 所有 doubles 在 $[1..k]$ 里都凑成对——条件 (b) 完全取决于数组排列，不单调，bit-trick 没救。

✅ 重新设计：让 $T$ 的 count 落在贡献奇偶分界点 $2 \to 3$

被这个反例打醒以后回去想，关键是奇偶性技巧。每个值对 $\text{len} - \text{res}$ 的贡献只看 count，count = 3 那档唯一贡献奇数。所以谓词应该让 $T$ 的 count 在 $k$ 跨过 $p_2$ 时正好从偶（=2）跳到奇（=3）。

解法：强制把 $p_1$ 和 $p_3$ 塞进询问当 baseline，让 $T$ count 起步 = 2；可变前缀 $[p_1+1..k]$ 决定 $p_2$ 进不进来。doubles 全偶贡献，自动失声。

这一刻才意识到为什么 Easy 给 50 次而 Hard 卡 33 次——Hard 是逼你想出贡献奇偶表那张图，否则你写一段「 $\text{res} == 0$ 」走 32 次询问的解法在 Easy 能水过去（其实也水不过去因为不收敛 ），但 Hard 必须靠奇偶性拿满 11 + 11 + 11。

❌ 第二版：query 函数签名想得不干净

写了个 query(pos1, to, pos1, pos3) 4-arg 重载，意思是 [pos1..to] ∪ {pos1, pos3}。Claude 提醒 pos1 重复传了（既是区间端点又是 extra），但实测因为内部用 set<ll> 去重，功能上没坏。算是一个"看起来丑但实际能跑"的设计——code review 视角不优雅，但提交跑下来对的，就先不动它了。

❌ 第三版：to 没卡上界 → MLE on test 2

写完 $p_2$ 那段提交：MLE on test 2，262100 KB / 256 MB。看了一会想不通：算法里 vector<ll> 都是局部变量，每次 query 完就析构，per-query 内存几 KB，单次 Solve $\le$ 100 KB，怎么会到 256 MB？

最后定位到 line 173 没卡 to < pos3：

1
2
3
4
5
6

for (int i = __lg(pos3 - pos1); i >= 0; --i) {
    ll to = pos2 + (1ll << i);
    // 没有越界保护！
    auto [len, res] = query(pos1, to, pos1, pos3);
    ...
}

bit-trick 推进时，trial 值 to 可以超过 pos3 甚至 N = 2n+1——比如 $p_3 \approx 2000$ , $p_{2,\text{actual}} \approx 1500$ , $p_1 = 1$ 这种局，几次 take 之后 pos2 ~ 1985，下一轮 $i=5$ 算出 to = 2017 > N，把 $2002, ..., 2017$ 这种不存在的位置全发给 judge。Judge 返 -1，但代码不退出继续读流，stream 关掉以后所有 cin 都 fail（C++11+ 落 res = 0），predicate 退化成"按 k 奇偶决定 take"，状态彻底污染。

Per problem statement: After receiving such a response, your program should immediately terminate.

我没退出，导致后面跑成什么样都不可控——MLE 大概率是 stdout pipe 被 judge 关掉以后 iostream 缓冲区累积，或者多 test cases 在烂状态下连续跑出来的 cascade。根因是单次 invalid query 没立刻退出。

修法：

1
2

ll to = pos2 + (1ll << i);
if (to >= pos3) continue;          // ← 补这一行

顺手把 $p_3$ 段 if (k > N) continue; 和 $p_1$ 段 if (k < 1) continue; 也补了——这俩同样能越界，只是没造成 MLE。

❌ 第四版：p_1 段 bit-trick 写错变量

补完三处 continue 还过不了。再仔细看 $p_1$ 段：

1
2
3
4
5

for (int i = __lg(pos3); i >= 0; --i) {
    ll k = pos3 - (1ll << i);   // ← 用了 pos3 不是 pos1!
    ...
    if (...) pos1 = k;
}

bit-trick 降序的标准套路是每轮用当前的 pos1****（已经被前几轮压低过）减 $2^i$ 当 trial 值，让 pos1 单调下降收敛到 $p_{1,\text{actual}} + 1$ 。我写成 pos3 - (1ll << i)， $p_3$ 整个循环不变，每轮 trial 都是固定的 $p_3 - 2^i$ 那 11 个偏移量——根本不是 bit-trick，最后 pos1 等于最后一次 predicate 真的那个 $k$ ，几乎一定是 $p_3 - 1$ （除非 $p_{1,\text{actual}} = p_3 - 1$ ）。

为什么 sample 蒙过了：sample 是 $p_1 = 1, p_3 = 3$ ，循环只 2 轮，恰好 $i=0$ 时 $k = p_3 - 1 = 2$ 就是 $p_{1,\text{actual}} + 1$ ，pos1 = 2，pos1-- = 1。完美对的——但完全是巧合。

改成 ll k = pos1 - (1ll << i);，提交：AC。提交号 374001488。

总结一下踩过的坑

1. lambda 返回值丢了——低级 typo 但确实写过，下次 IDE warning 多看一眼

2. !res 不单调——奇偶谓词 vs 等于零谓词的认知差。等于零是偶发性的、依赖排列；奇偶性才是结构性的，doubles 自动失声

3. bit-trick trial 值没卡上界——3 个段都要保护：k > N / k < 1 / to >= p_3。MLE 不是因为单次内存，是因为没有遵守 read -1 → exit 的协议，状态污染后续的 cascade 才把内存搞炸的

4. bit-trick 用了静态变量代替累积变量——pos3 - 2^i vs pos1 - 2^i，sample 巧合下还能过，靠肉眼看完全看不出来，必须自己手算几个反例

5. Easy → Hard 不是单纯次数压紧——往往 Hard 在逼你换更结构化的 idea。这道题 Hard 的 33 次是直接告诉你"每段必须 $\lceil \log_2 N \rceil$ 不能浪费"，反推奇偶谓词的设计

附件

📄 p2 奇偶谓词的设计思路（独立讲解 PDF，含贡献奇偶表 + 反例数组完整 trace）

D2_Unique_Values_Hard_version.cpp.txt

📄 p2 奇偶谓词的设计思路（独立讲解 PDF，含贡献奇偶表 + 反例数组完整 trace）

D2_Unique_Values_Hard_version.cpp.txt

杭电 2026 春季联赛 7 第 1 题（HDU 1001）。原题：https://acm.hdu.edu.cn/contest/problem?cid=1203&pid=1001

题目大意

无向连通图 $n$ 点 $m$ 边，每条边有正权 $w$ 表示走这条边耗费的时间。每个点 $i$ 上有一瓶魔力药水 $a_i$ ，喝一瓶可以让魔力值 $\pm a_i$ （任意次、不耗时间）。从 $1$ 号点出发、初始魔力 $0$ ，目标让魔力值恰好等于 $V$ ，求最少总移动时间；不可达输出 -1 。

约束 $1 \le n, m \le 10^4$ ， $1 \le V, a_i, w \le 10^9$ 。题面保证 $a_1$ 的所有质因数都在 $V$ 的质因数集合中（注意这不蕴含 $a_1 \mid V$ ）。

样例

1
2
3
4
5

1
3 2 18
2 3 4
1 2 10
2 3 20

输出 0 。 $V = 18 = 9 \cdot a_1$ ，起点直接喝 9 次正向药水就行，不用动。

思路讲解

一句话

走过的点的 $a_i$ 通过裴蜀定理可以拼出 $\gcd$ 的所有倍数；问题等价于找一条从 $1$ 出发的路径，让经过点的 $\gcd$ 整除 $V$ ，最小化总边权。 $\gcd$ 状态只有 $O(\log V)$ 种，分层图 Dijkstra 直接跑。

裴蜀定理转化

走过点集 $S$ 时，每个点 $i \in S$ 都可以喝若干次正向 / 反向药水。最终魔力值是

$\sum_{i \in S} k_i \cdot a_i, \quad k_i \in \mathbb{Z}.$

也就是关于 $\{a_i\}_{i \in S}$ 的整数线性组合。

🧮 Note: 裴蜀定理（Bézout）： $\{a_i\}$ 的整数线性组合恰好覆盖 $\gcd(a_i : i \in S)$ 的全部整数倍。

所以走过点集 $S$ 的可达魔力值集合 $=$ $\gcd(a_i : i \in S)$ 的全体整数倍。目标 $V$ 可达 等价于 $\gcd(S) \mid V$ 。

殊途同归一句：经过一个点不强制喝它的药水，但跳过 $=$ 把它从计入 gcd 的集合里去掉，gcd 只会变大、整除关系只会更难满足。所以最优策略就是把走过的点全喝，状态干脆只追"目前路径上点的 gcd"一个量。

gcd 的状态数 $=$ $O(\log V)$

• 起点 gcd $= a_1$

• 每加入一个新点 $v$ ， gcd 变成 $\gcd(g, a_v)$ ：要么不变（ $a_v$ 是 $g$ 的倍数），要么至少缩小一半（变成 $g$ 的真因子）

从 $a_1$ 一路降到 $1$ 最多 $\log_2 a_1 = O(\log V)$ 步。出现过的 gcd 全是 $a_1$ 的因数，每个节点最多 $O(\log V)$ 种 gcd 状态。

关键不变量：状态空间上界 $n \cdot O(\log V) \approx 10^4 \cdot 30 = 3 \times 10^5$ ，分层图 Dijkstra 完全跑得动。

分层图 Dijkstra

状态 $(u, g)$ ：当前在节点 $u$ 、当前路径上点的 gcd 是 $g$ 。

转移：从 $(u, g)$ 沿边 $(u, v, w)$ 到 $(v, \gcd(g, a_v))$ ， dist 加 $w$ 。

起点 $(1, a_1)$ ， dist $= 0$ 。

答案：扫所有可达状态 $(u, g)$ ，其中满足 $V \bmod g = 0$ 的最小 dist 即为答案。

边权全正、状态空间有限，标准 Dijkstra（pq + lazy stale check）就够。

实现要点

• 用 vector<map<ll, ll>> mp(n+2) 存每个节点的 gcd → dist

• pq pop 出来 必须 先判 step > mp[u][gcd] 跳过 stale 态——否则同一个状态反复被 push 出来展开邻居，状态量爆炸 TLE

• 起点先特判 V % a_1 == 0 直接输出 0

• 找到 ans 后加剪枝 step + w >= ans continue

• ans 永远是 LLONG_MAX 时输出 -1 ——题面保证 $a_1$ 的质因数 $\subseteq V$ 的质因数，但不蕴含 $a_1 \mid V$ ，反例 $a_1 = 4, V = 18$ 下若所有 $a_i \in \{4, 8, 12, \dots\}$ 永远凑不出 $18$ ，必须返回 -1

AC 代码

AC 提交链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

// teamname: Gospel_rock
/**
 * Problem: Card
 * Contest: 2026 杭电春季联赛 7
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1203&pid=1001
 * Created: 2026-05-08 22:53:45
 * Author: Gospel_rock
 */

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

struct UStepGcd {
    ll u, gcd, step;
    bool operator<(const UStepGcd &o) const { return step > o.step; }
};

void Solve() {
    ll N, M, V;
    cin >> N >> M >> V;
    vector<ll> A(N + 2);
    vector<vector<array<ll, 2>>> g(N + 2);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= M; ++i) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    if (V % A[1] == 0) { cout << 0 << "\n"; return; }
    priority_queue<UStepGcd> pq;
    pq.push({1, A[1], 0});
    vector<map<ll, ll>> mp(N + 2);
    ll ans = LLONG_MAX;
    while (!pq.empty()) {
        auto [u, gcd, step] = pq.top();
        pq.pop();
        if (step > mp[u][gcd]) continue;
        for (auto [v, w] : g[u]) {
            ll to_gcd = __gcd(A[v], gcd);
            if (V % to_gcd == 0) ans = min(ans, step + w);
            if (step + w >= ans) continue;
            if (!mp[v].contains(to_gcd) || step + w < mp[v][to_gcd]) {
                mp[v][to_gcd] = step + w;
            } else {
                continue;
            }
            pq.push({v, to_gcd, step + w});
        }
    }
    if (ans == LLONG_MAX) { cout << -1 << "\n"; return; }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) Solve();
    return 0;
}

心路历程（TLE → WA → AC）

第一版 TLE

priority_queue + map<ll, map<ll, ll>> 直接交，TLE 。原因：

• pop 出来没做 stale check ，直接处理邻居 → 同一个 (u, g) 状态被反复 push、pop、展开邻居，pq 状态量指数膨胀

• map<ll, map<ll, ll>> 嵌套红黑树，每次 contains / operator[] 都是 O(log²) ，常数惨

修法：

1. pop 之后立刻 if (step > mp[u][gcd]) continue;

2. 外层换成 vector<map<ll, ll>> （节点下标天然是 vector 索引）

3. 顺手加 step + w >= ans 早剪枝

第二版 WA

修完 TLE 跑通样例，交上去 WA 。原因：

• ll ans = LLONG_MAX ，不可达时没转 -1 直接打印了 9223372036854775807

• 题面要求不可达输出 -1

修法：

1

cout << (ans == LLONG_MAX ? -1 : ans) << "\n";

题面"保证 $a_1$ 的质因数 $\subseteq V$ 的质因数"乍看像在保证可达，其实不蕴含 $a_1 \mid V$ ：例如 $a_1 = 4, V = 18$ ， $\{2\} \subseteq \{2, 3\}$ 满足前提，但 $4 \nmid 18$ 。如果整张图所有 $a_i$ 都是 $4$ 的倍数（gcd 永远是 $4$ 的倍数）就永远凑不出 $18$ ，必须返回 -1 。

加上这一行后 AC 。

附件

（暂无）

题目大意

CCPC 2023 Guangdong Provincial M - Computational Geometry（CF Gym 104369 镜像）。

给定逆时针顺序凸 $N$ 边形顶点 $A_0, A_1, \ldots, A_{N-1}$ ，选两个不相邻的顶点 $A_{i_1}, A_{j_1}$ 把多边形切成两段 sub-polygon $Q$ 和 $R$ ，最小化

$$\mathrm{diam}(Q)^2 + \mathrm{diam}(R)^2$$

数据范围 $N \le 5000$ ，多组数据。

样例

• $N = 4$ ， $\{(1,0), (2,0), (1,1), (0,0)\}$ ，期望 $\mathbf{4}$ ：切 $(0, 2)$ 把菱形切成两个三角形，每半 $d^2 = 2$ 。

• $N = 6$ ，spike-3 hull，期望 $\mathbf{44}$ ：切 $(2, 4)$ ， $Q$ 直径 $^2 = 10$ 、 $R$ 直径 $^2 = 34$ 。

思路讲解

普通 RC 求凸多边形直径为什么对

直观理解：拿一把卡尺（两条平行 supporting line）夹住凸多边形旋转一圈，最大间距就是直径。算法上对应「外循环 r 跑遍每条边、内层 l 跟随推进」——每条边都被卡过一遍，所以直径必出现在某次「边-反极顶点」的 candidate 里，必被 collect。

本题改造为什么有问题——边覆盖不全

子弧 + 闭合 chord 是一个闭子多边形 $R'$ ，对它跑经典 RC 是对的——但前提是把 $R'$ 的所有边都卡过。

我的改造里 edge 从 $i$ 起步靠 need_edge_move 单调向前推进，永远停留在原多边形的相邻顶点对 $(A_e, A_{e+1})$ 上。但 $R'$ 的边集 = 子弧上的原边 + 一条非相邻的 chord $(A_j, A_i)$ ——chord 是非相邻顶点对，edge 数值永远不会取到它。

卡尺没把 $R'$ 的所有边卡过一遍，自然漏直径。

区间 DP 正解

状态

$\mathrm{dp}[i][j]$ = 以子弧 $A_i \to A_{i+1} \to \cdots \to A_j$ （CCW 沿原多边形顺序，含两端）为顶点集的闭子多边形的直径² ——即该顶点集上所有点对的 $\|A_p - A_q\|^2$ 最大值。

递推

$$\mathrm{dp}[i][j] = \max\big(\,\mathrm{dp}[i{+}1][j],\ \mathrm{dp}[i][j{-}1],\ \|A_i - A_j\|^2\,\big)$$

正确性：把顶点集 $\{i, i{+}1, \ldots, j\}$ 上所有无序点对 $(p, q)$ 按是否含两端点 $i, j$ 分三类：

• 不含 $i$ ：点对 $\subseteq \{i{+}1, \ldots, j\}$ ，覆盖在 $\mathrm{dp}[i{+}1][j]$

• 不含 $j$ ：点对 $\subseteq \{i, \ldots, j{-}1\}$ ，覆盖在 $\mathrm{dp}[i][j{-}1]$

• 两端都含：唯一点对 $(i, j)$ ，单独的 $\|A_i - A_j\|^2$ 项

三类不重不漏、取 max 即全集直径²。

为什么 DP 走得通、RC 走不通

关键对比：这个递推式完全不依赖凸性——它就是个「枚举所有点对取 max」的 $O(N^2)$ 朴素 DP。「凸」在 RC 路线里是刚需（卡尺单峰让对蹵点单调推进 → $O(N)$ ）；DP 路线不贪「凸」这点便宜、只用上「顶点集是连续子弧」这个事实。一句话：RC 吃结构红利换 $O(N)$ ，DP 不吃红利 $O(N^2)$ 但保命。

循环顺序是硬约束

跟一般区间 DP 一样：len 在外、 $i$ 在内。奇心把 $i$ 写在外会踩心路历程 7 那个坑（ $2N$ pass 兜底也救不回）。

切法枚举

枚举不相邻顶点对 $(i_1, j_1)$ 作为 chord：

$$\mathrm{ans} = \min_{j_1 \ge i_1 + 2,\ j_1 \not\equiv i_1 \pm 1 \pmod N} \big(\,\mathrm{dp}[i_1][j_1] + \mathrm{dp}[j_1][i_1]\,\big)$$

两项分别是切后两段子弧的直径²——dp 表索引是循环的， $\mathrm{dp}[j_1][i_1]$ 自动覆盖另一段。cross 检查 $\ne 0$ 顺手筛掉两类退化： wrap-adjacent切（如 $(0, N-1)$ 在循环视角下其实是相邻点），与共线退化切（chord 踩在原多边形某条边上）。

复杂度

填 dp 表 $O(N^2)$ 个状态 × $O(1)$ 转移、枚举切法 $O(N^2)$ 、总 $O(N^2)$ 。 $N \le 5000$ 下填表 $2.5 \times 10^7$ 次贴近 TL，多组数据下实测 3312 ms / 6s 限制。

AC 代码

AC 提交：codeforces.com/gym/104369/submission/373844988

切到 $O(N^2)$ 区间 DP 后 AC（3312 ms / 192600 KB， $N \le 5000$ 多组数据贴近 TL）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// dp[i][j] = 子弧 A_i → A_j（CCW，含两端）的凸子多边形直径²
// 递推：dp[i][j] = max(dp[i+1][j], dp[i][j-1], ‖A_i - A_j‖²)
// 关键：len 外、i 内 —— len 大的依赖 len 小的，i 在外的话同 len 不同起点的
//       dp[i+1][·] 还没填过，单遍跑不出来；2N pass 兜底也是错觉

auto distancePPNorm(const Point &a, const Point &b) {
    return (a - b).norm();  // 返回平方距离，不开根
}

void Solve() {
    ll N;
    cin >> N;
    vector<Point> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    vector<vector<ull>> dp(N, vector<ull>(N));
    for (int len = 1; len < N; ++len) {
        for (int i = 0; i < N; ++i) {
            int ip1 = (i + 1) % N;
            int j = (i + len) % N;
            int j_1 = (i + len - 1) % N;
            if (len == 1) { dp[i][j] = distancePPNorm(A[i], A[j]); continue; }
            dp[i][j] = max({dp[ip1][j], dp[i][j_1], (ull) distancePPNorm(A[i], A[j])});
        }
    }
    // 枚举切法 (i1, j1)，分多边形为子弧 [i1..j1] 与 [j1..i1+N]
    ull ans = ~0ULL;  // ⚠️ 不能用 INF=(1ll<<61)-1，被 1.6e19 候选反超 → WA on test 7
    for (int i1 = 0; i1 < N; ++i1) {
        int j2 = i1;
        for (int j1 = i1 + 2; j1 < N; ++j1) {
            int i2 = j1;
            // cross != 0 顺手筛掉 wrap-adjacent (0, N-1) 与共线退化切
            if (cross(A[i1], A[(i1+1)%N], A[j1]) != 0
             && cross(A[i2], A[(i2+1)%N], A[j2]) != 0) {
                ans = min(ans, dp[i1][j1] + dp[i2][j2]);
            }
        }
    }
    cout << ans << "\n";
}

心路历程

1. 直觉把「凸多边形直径 → 旋转卡壳」和「切法枚举」硬嫁接，写出 vanilla RC + 子弧增长版

2. sample 1 ( $n=4$ ) 期望 $4$ 实测 $3$ ，开始 debug

3. 第一发现： $\mathrm{dp}[2][0] = 1$ 漏了 $(A_2, A_3)$ 这对距离——up 起步 $i+2$ ，arc 起点附近的 pair 永远不进 candidate

4. 第二发现：dp[edge][up] = ans 索引用动态 edge 而非外层切起点 $i_\mathrm{outer}$ ，dp 矩阵大量被错位写入（附带 bug）

5. spike-3 对拍反例（差 $7.45\%$ ）让「算法是结构性错的、不是 off-by-one」心服口服

6. 抓到根因：RC 之所以对，因为它每条边都卡过 + 每个顶点都反极过；改造版两条都破了

7. DP 重写又踩循环顺序坑——RC 死了之后转 $O(N^2)$ 区间 DP（ $\mathrm{dp}[i][j]$ = 子弧 $A_i \to A_j$ 凸子多边形直径² ），递推 $\mathrm{dp}[i][j] = \max(\mathrm{dp}[i+1][j],\ \mathrm{dp}[i][j-1],\ \|A_i - A_j\|^2)$ 。第一发先把 $i$ 写在外、 $\mathrm{len}$ 写在内，再跑 $2N$ 遍当兜底——错：

• 当前算 $\mathrm{dp}[i][j]$ 需要 $\mathrm{dp}[i+1][j]$ （len $-1$ 但起点变了）。 $i$ 外 len 内的顺序下，处理 $i=0$ 时 $\mathrm{dp}[1][\cdot]$ 整行都还是 $0$ ，根本没轮到 $i=1$ 那层
• $2N$ pass 兜底也救不回来：pass 1 全程用 $0$ 推导出脏值；pass 2 处理 $i=0,\ \mathrm{len}=3$ 时要 $\mathrm{dp}[1][3]$ ，可这个值是 pass 1 用 $\mathrm{dp}[2][3]=0$ 算出来的脏值——pass 2 来不及修
• 正确写法：len 外、 $i$ 内，一遍即可

心法：「len 小的之前都被计算了」这个直觉成立的前提是 len 在外。 $i$ 在外的话，给定 $i$ 你确实按 len 升序填了 $\mathrm{dp}[i][\cdot]$ ，但同 len 不同起点的 $\mathrm{dp}[i+1][\cdot]$ 还压根没碰过——「 $2N$ pass 兜底」是错觉：每跑一遍正确性最多渗透一层 len，最坏要 $N$ 遍且仍受脏值污染。

附件

详细 debug 记录与图示见下方嵌入 PDF —— rc_breakdown.pdf ，5 页，含凸多边形 + 反极顶点单峰示意 / 闭子多边形 $R'$ / forbidden up + chord $\times$ 标记 / $\mathrm{dp}[3][1]$ trace 表。

rc_breakdown.pdf — 5 页 debug 记录：经典 RC 为什么对（凸多边形 + 反极顶点 + 距离单峰）/ 闭子多边形 R’ / forbidden up + chord ✗ 标记 / dp[3][1] trace 表

🤖 Claude 苏格拉底式带教对话录原稿。每一步都是 mentor 提一个聚焦问题 → me 答 → 反复推进至完整算法。蓝色 callout 是 Claude，橙色 callout 是 zzy，原稿里 mentor 的反例 / 矫枉过正 / 用户吐槽全部逐字保留。

原题：洛谷 P3187 [HNOI2007] 最小矩形覆盖（紫题）](https://www.luogu.com.cn/problem/P3187)（紫题）)

📝 大对话录正文 + AC 代码 + 附件随后通过 raw API patch 进来。

🤖 Claude 苏格拉底式带教对话录原稿。每一步都是 mentor 提一个聚焦问题 → me 答 → 反复推进至完整算法。蓝色 callout 是 Claude，橙色 callout 是 zzy，原稿里 mentor 的反例 / 矫枉过正 / 用户吐槽全部逐字保留。

原题：洛谷 P3187 [HNOI2007] 最小矩形覆盖（紫题）

背景

题目链接：洛谷 P3187 [HNOI2007] 最小矩形覆盖。

题面要点：给定平面上 $n$ 个点，求一个 覆盖所有点的最小面积矩形（矩形可以任意旋转，不要求轴对齐），输出面积和按逆时针的四个顶点。约束 $3 \le n \le 5\times 10^4$ ，坐标 $\in [0,10]$ ，最小矩形面积至少 $0.1$ ，误差容忍 $10^{-4}$ 。

下面按对话方式逐步推进。蓝色 标注首次出现的关键术语 / 符号。

第 1 步：理解题目

🤖 Note:
Claude (Mentor)
先用样例热身。 $n=6$ 个点

$$(1,3),\ (1,4),\ (2,1),\ (3,0),\ (3,6),\ (6,3),$$

标程给的最小矩形顶点是 $(3,0), (6,3), (3,6), (0,3)$ ，面积 $18$ 。
画一下图（或在脑里走一遍）：这 4 个矩形顶点和原始 6 个点放在一起。原始 6 个点里，有几个落在矩形边界上？分别在哪条边上？（不在边上的就是严格落在矩形内部）
这一步只是想让你看清楚"最小矩形"长什么样——为后面想算法做铺垫。

🧑 Note:
zzy (Me)
这个样例数据范围比较小，不过 $O(n)$ 的算法应该可以做到。然后这个理解题目不是很重要，毕竟这个题目是一道模板题，描述非常简单。再说了，我也没法告诉你，我也不想画这个图，你自己把这个图画出来，用 LaTeX 画出来。

🤖 Note:
Claude (Mentor)
好——我把图补上，复杂度修正一下，然后跳到下一步。
样例可视化：绿色填充多边形 = 输入 6 点的凸包（CCW 顺序 $(3,0)\to(6,3)\to(3,6)\to(1,4)\to(1,3)\to(2,1)$ ，6 边形）；蓝色 outline = 标程给的最小覆盖矩形；蓝环 = 矩形 4 顶点；红实心点 = 输入 6 点。
\begin{center}
\begin{tikzpicture}[scale=0.78]
\draw[help lines, gray!25] (-0.5,-0.5) grid (6.5,6.5);
\draw[->, gray!60] (-0.7,0)–(7.0,0) node[right, black]{\scriptsize $x$ };
\draw[->, gray!60] (0,-0.7)–(0,7.0) node[above, black]{\scriptsize $y$ };
\foreach \i in {1,2,3,4,5,6} {
\draw[gray!60] (\i,0.05)–(\i,-0.05) node[below=1pt, black]{\tiny \i};
\draw[gray!60] (0.05,\i)–(-0.05,\i) node[left=1pt, black]{\tiny \i};
}
\fill[green!30, opacity=0.55]
(3,0) – (6,3) – (3,6) – (1,4) – (1,3) – (2,1) – cycle;
\draw[green!50!black, very thick]
(3,0) – (6,3) – (3,6) – (1,4) – (1,3) – (2,1) – cycle;
\draw[blue!70!black, very thick] (3,0) – (6,3) – (3,6) – (0,3) – cycle;
\foreach \pt in {(3,0), (6,3), (3,6), (0,3)} {
\draw[blue!70!black, very thick] \pt circle (5pt);
}
\foreach \pt in {(1,3), (1,4), (2,1), (3,0), (3,6), (6,3)} {
\fill[red!85!black] \pt circle (2.6pt);
}
\node[blue!50!black, font=\tiny, anchor=north] at (3.0, -0.45) { $(3,0)$ };
\node[blue!50!black, font=\tiny, anchor=west] at (6.30, 3.0) { $(6,3)$ };
\node[blue!50!black, font=\tiny, anchor=south] at (3.0, 6.35) { $(3,6)$ };
\node[blue!50!black, font=\tiny, anchor=east] at (-0.30, 3.0) { $(0,3)$ };
\node[red!70!black, font=\tiny, anchor=south] at (1.0, 4.20) { $(1,4)$ };
\node[red!70!black, font=\tiny, anchor=north] at (1.0, 2.78) { $(1,3)$ };
\node[red!70!black, font=\tiny, anchor=west] at (2.20, 1.0) { $(2,1)$ };
\node[blue!55!black, font=\scriptsize] at (4.4, 5.0) {最小矩形};
\node[green!40!black, font=\scriptsize] at (2.5, 2.5) {凸包};
\end{tikzpicture}
\end{center}
对照：6 输入点全部在凸包上（凸包就是这 6 个点）。其中 3 个 $(3,0),(3,6),(6,3)$ 同时也是矩形顶点； $(1,4)$ 落在矩形顶边 $(3,6)\!-\!(0,3)$ 上； $(2,1)$ 落在左边 $(0,3)\!-\!(3,0)$ 上； $(1,3)$ 是凸包顶点但严格在矩形内部。凸包和矩形的偏差区 = 矩形里没被凸包覆盖到的两块小三角，分别贴在 $(0,3)$ 那个"空角"两侧（绿色和蓝色 outline 不重合的部分肉眼可见）。
复杂度修正： $n \le 5\times 10^4$ ，本题 $O(n)$ 严格地说做不到——求凸包要 sort 是 $O(n\log n)$ 。凸包给定后的旋转卡壳那部分确实是 $O(h)$ 。所以全流程 $\boldsymbol{O(n\log n)}$ 。这里 $h$ 表示凸包顶点数。

第 2 步：核心引理 + 暴力骨架

🤖 Note:
Claude (Mentor)
跳到算法骨架。模板的根本依赖是把矩形 方向（连续的 $[0, \pi/2)$ 角度）离散化到有限多个候选——这一步靠的是一条几何引理。
我先把它抛出来给你确认：
核心引理：覆盖凸包的最小面积矩形，至少有一条边与凸包的某条边共线。
先问一个问题：接受这条引理后，你能直接说出一个暴力算法吗——枚举什么、对每个枚举对象做什么、整体复杂度多少？

🧑 Note:
zzy (Me)
不是啊，哪有你这么讲题，让我先接受一个引理啊，这个引理怎么来的？我接受了吗？你代替我接受了是吧？我们也不用严格的证明对吧？但是你不能直接跳过这个引理是怎么来的吧，你这也太搞笑了吧。

🧑 Note:
zzy (Me)
不是啊，你就算这个证明，也需要引导我一次性写出太多东西也是禁止行为。任何回答都必须有引导性，不能一次性吐出太多内容。一次性吐出太多内容是绝对禁止的，懂吗。

🤖 Note:
Claude (Mentor)
懂了，回单步引导。
先做一个具体观察，不抛任何理论。在你刚才那张样例图上数：
最小矩形的 4 条边，每条边上各自经过几个凸包顶点？（提醒：这个样例的凸包顶点 = 全部 6 个输入点——之前在图下方写过——所以你只需要数 6 个红点分别落在哪条矩形边/角上。）

🧑 Note:
zzy (Me)
我们也都知道，我们需要解决的问题是什么，就是我们想要证明的就是至少有一条边是和凸包的边是平行的，或者说其实是重合的吧，其实是重合的。就是我们的这个最小覆盖矩形…

🤖 Note:
Claude (Mentor)
对，重合（collinear / 同一条直线上）比"平行"强——平行只锁方向，重合还锁位置。这就是引理要证的精确陈述。
回到我刚问那个图的问题，因为它直通证明：在图上数，最小矩形的 4 条边，每条边各自经过几个凸包顶点？

🧑 Note:
zzy (Me)
每条边至少都经过了至少两个红点对，每条边都经过了两个红点。

🤖 Note:
Claude (Mentor)
对，每条边恰好 2 个凸包顶点——这是个很硬的结构信号。
下一个微观察：刚才数出来的"矩形某条边上的 2 个凸包顶点"，比如最小矩形底边上的 $(3,0)$ 和 $(6,3)$ ——它们在凸包上是相邻的吗？也就是说，凸包的顶点序列里，它们俩之间是不是直接由一条凸包边连接、中间没有插入别的凸包顶点？

🧑 Note:
zzy (Me)
对，当然是相邻的，当然是相邻的。

🤖 Note:
Claude (Mentor)
好。底边 $(3,0)\!-\!(6,3)$ 上的 2 个凸包顶点相邻 $\Rightarrow$ 底边完整包含凸包边 $(3,0)\!\to\!(6,3)$ $\Rightarrow$ 底边和该凸包边重合（共线）。引理在这个样例里被超额满足——4 条边全部重合于某条凸包边。
切换到一般情形思考（这个样例太特殊）。把凸包想成一个一般、不对称的凸多边形，外接最小覆盖矩形。
反证 setup 一步：假设最小覆盖矩形没有任何一条边和凸包某条边重合。那么矩形每条边和凸包的接触应该是几个点？

🧑 Note:
zzy (Me)
如果假设最小覆盖矩形没有任何一条边和凸包某条边重合，那么矩形每条边和凸包的接触点就只有一个点嘛，每条边和凸包的接触点最多只有一个点。

🤖 Note:
Claude (Mentor)
对——准确说是恰好 1 个点：

• " $\le 1$ "是反证假设直接给的（不重合 $\Rightarrow$ 不会经过 2 个相邻凸包顶点；非相邻 2 个顶点更不可能在同一条支撑切线上）。
• " $\ge 1$ “是因为矩形必须紧贴凸包：如果某条边一个凸包顶点都不接触，那条边就能往凸包内推一点，矩形面积变小——它就不是最小的了，矛盾。
  所以 4 条矩形边各自接触凸包恰好 1 个顶点，命名为 支撑顶点 $L, R, T, B$ （左/右/上/下边对应）。
  下一步问题：在 $L, R, T, B$ 这 4 个支撑顶点固定不变的前提下，矩形"覆盖凸包、 $L,R,T,B$ 各自落在对应矩形边上”——还剩几个自由度？也就是说，可以怎样扰动这个矩形让它仍然满足这两个条件？

🧑 Note:
zzy (Me)
LRTB 各自落在对应矩形边上，此时还剩几个自由度。嗯，什么叫几个自由度？不太懂你意思，这几个自由度是什么意思啊？不太懂。

🤖 Note:
Claude (Mentor)
好，“自由度"说人话——
自由度 = 保持约束（这里=” $L,R,T,B$ 各自落在对应矩形边上"）的前提下，矩形还能怎么动。能独立动几个方向就是几个自由度。
举例：

• 一个无约束的矩形在平面上有 5 个自由度——中心 2D（2）+ 旋转角（1）+ 宽（1）+ 高（1）。
• 加约束"中心必须在原点" $\Rightarrow$ 砍掉 2 个 $\Rightarrow$ 剩 3 个自由度。每加 1 个独立约束就砍 1 个自由度。
  重新具体问：4 支撑顶点 $L, R, T, B$ 固定。如果我把矩形逆时针旋转一个小角度 $\epsilon$ ，同时重新调整它的位置/宽/高（不局限于原参数），让 $L, R, T, B$ 仍然分别落在新矩形对应的 4 条边上——这样的新矩形存在吗？（提示：每条新矩形边应该是过对应支撑点、方向沿着新旋转角的那条切线。）

🧑 Note:
zzy (Me)
应该是存在的，就是旋转一个小角度，肯定是可以的。

🤖 Note:
Claude (Mentor)
对——所以 4 支撑固定时，矩形只剩 1 个自由度：旋转角 $\theta$ 。每个 $\theta$ 唯一确定一个矩形（4 条边各自就是过 $L,R,T,B$ 沿对应方向的切线），矩形的宽、高、面积都成了 $\theta$ 的（光滑）函数： $\text{width}(\theta)$ 、 $\text{height}(\theta)$ 、 $A(\theta)$ 。当前矩形对应 $\theta = \theta_0$ 。
关键问题：反证假设 “当前矩形是最小的” $\Rightarrow$ $A(\theta)$ 在 $\theta_0$ 处取局部极小。这给一阶导数 $A'(\theta_0)$ 一个什么必要条件？

🧑 Note:
zzy (Me)
那这个一阶导数 $A'(\theta_0)$ 理论上应该等于 0 对吧，因为这个极值点嘛，极值点它肯定这个导数值为 0 嘛。

🤖 Note:
Claude (Mentor)
对， $A'(\theta_0) = 0$ 是必要条件。但单凭这个还推不出矛盾—— $A' = 0$ 既可以是极小、也可以是极大或鞍点。要把矛盾构造出来，得继续做二阶或结构性分析。
为了往下走，先把 $A(\theta)$ 显式写出来。
记号：