洛谷 P3187 - [HNOI2007] 最小矩形覆盖 · znzryb
> 🤖 **Claude** 苏格拉底式带教对话录原稿。每一步都是 mentor 提一个聚焦问题 → me 答 → 反复推进至完整算法。蓝色 callout 是 Claude，橙色 callout 是 zzy，原稿里 mentor 的反例 / 矫枉过正 / 用户吐槽全部逐字保留。
原题：[洛谷 P3187 [HNOI2007] 最小矩形覆盖]([https://www.luogu.com.cn/problem/P3187)（紫题）](https://www.luogu.com.cn/problem/P3187)（紫题）)
> 📝 大对话录正文 + AC 代码 + 附件随后通过 raw API patch 进来。
> 🤖 **Claude** 苏格拉底式带教对话录原稿。每一步都是 mentor 提一个聚焦问题 → me 答 → 反复推进至完整算法。蓝色 callout 是 Claude，橙色 callout 是 zzy，原稿里 mentor 的反例 / 矫枉过正 / 用户吐槽全部逐字保留。
原题：[洛谷 P3187 [HNOI2007] 最小矩形覆盖](https://www.luogu.com.cn/problem/P3187)（紫题）
<!-- Notion block type: table_of_contents -->
## 背景
题目链接：[洛谷 P3187 [HNOI2007] 最小矩形覆盖](https://www.luogu.com.cn/problem/P3187)。
**题面要点**：给定平面上 $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)$ 显式写出来。
**记号**：
- $\boldsymbol{u} = R - L$ （"左右"支撑顶点之差，固定向量），
- $\boldsymbol{v} = T - B$ （"上下"支撑顶点之差，固定向量），
- $\hat{n}_\theta = (\cos\theta, \sin\theta)$ （矩形"水平"单位方向），
- $\hat{n}_\theta^{\perp} = (-\sin\theta, \cos\theta)$ （"垂直"方向，与 $\hat{n}_\theta$ 正交）。
**下一步问题**：在这个记号下，矩形的*宽* $\text{width}(\theta)$ 等于 **什么内积**？*高* $\text{height}(\theta)$ 等于**什么内积**？（提示：宽就是把所有凸包顶点投影到 $\hat n_\theta$ 方向后的"最右"减"最左"——但因为左右支撑就是 $L, R$ ，"最右"投影 $= R \cdot \hat n_\theta$ 、"最左" $=L \cdot \hat n_\theta$ 。）
> 🧑 **Note**:
**zzy (Me)**
建议你还是把图画出来比较好。你画一个图，我能更清楚地看到这些量。注意画图要检查啊，要检查。然后还有推荐绘图方式好吧。
> 🤖 **Note**:
**Claude (Mentor)**
好，画一张一般情形的示意图。
**图设定**：
- 凸包：6 顶点不对称凸六边形，CCW $H_1\!=\!(3,3),H_2\!=\!(7,2),H_3\!=\!(9,5),H_4\!=\!(8,8),H_5\!=\!(5,9),H_6\!=\!(2,6)$ 。
- 取 $\theta = 30^\circ$ ：算出 $L=H_1,\ R=H_4,\ T=H_5,\ B=H_2$ 。*选 $30^\circ$ 而非更小的角度*是为了把旋转视觉上拉够大——任何 $\theta \in (18.43^\circ, 71.57^\circ)$ 都属于同一段平滑段（4 支撑不变），但 $\theta$ 接近段端点时矩形看起来会和凸包某条边伪 flush，误导读者以为"它们已经重合"； $30^\circ$ 离两端均够远。
- 矩形：通过 4 条支撑切线方程算出 4 顶点。
\begin{center}
\begin{tikzpicture}[
scale=0.62, font=\footnotesize,
spt/.style={circle, fill=red!85!black, inner sep=0pt, minimum size=5.5pt},
splbl/.style={red!75!black, font=\small\bfseries},
]
\coordinate (H1) at (3,3); \coordinate (H2) at (7,2); \coordinate (H3) at (9,5);
\coordinate (H4) at (8,8); \coordinate (H5) at (5,9); \coordinate (H6) at (2,6);
\coordinate (BL) at (4.43, 0.52); \coordinate (BR) at (10.35, 3.93);
\coordinate (TR) at (6.82, 10.05); \coordinate (TL) at (0.90, 6.63);
\draw[help lines, gray!18] (-0.5,-0.5) grid (11.0,11.0);
\fill[green!25, opacity=0.55]
(H1) -- (H2) -- (H3) -- (H4) -- (H5) -- (H6) -- cycle;
\draw[green!50!black, very thick]
(H1) -- (H2) -- (H3) -- (H4) -- (H5) -- (H6) -- cycle;
\draw[blue!65!black, very thick] (BL) -- (BR) -- (TR) -- (TL) -- cycle;
\draw[->, orange!85!black, line width=1.2pt] (H1) -- (H4)
node[pos=0.30, sloped, above=2pt, orange!60!black, font=\small]{ $\bm u = R\!-\!L$ };
\draw[->, violet!80!black, line width=1.2pt] (H2) -- (H5)
node[pos=0.72, sloped, above=2pt, violet!55!black, font=\small]{ $\bm v = T\!-\!B$ };
\node[spt, label={[splbl, label distance=-3pt]below left: $L$ }] at (H1) {};
\node[spt, label={[splbl, label distance=-3pt]above right: $R$ }] at (H4) {};
\node[spt, label={[splbl, label distance=-1pt]above: $T$ }] at (H5) {};
\node[spt, label={[splbl, label distance=-1pt]below: $B$ }] at (H2) {};
\coordinate (O) at (0.0, 0.4);
\draw[gray!45, thin] (O) -- ++(1.7, 0);
\draw[->, blue!55!black, line width=1pt] (O) -- ++(1.30, 0.75)
node[right=1pt, font=\scriptsize, blue!55!black]{ $\hat n_\theta$ };
\draw[->, blue!55!black, line width=1pt] (O) -- ++(-0.75, 1.30)
node[above=1pt, font=\scriptsize, blue!55!black]{ $\hat n_\theta^{\perp}$ };
\draw[gray!60, thin] ( $(O)+(0.9,0)$ ) arc (0:30:0.9);
\node[gray!45!black, font=\scriptsize] at ( $(O)+(1.0,0.25)$ ) { $\theta$ };
\end{tikzpicture}
\vspace{2pt}
{\footnotesize\sffamily\color{gray} 图注：以 $\theta = 30^\circ$ 、不对称凸六边形为例。绿色多边形 = 凸包；蓝色矩形 = 旋转 $\theta$ 后的覆盖矩形；红点 $L,R,T,B$ = 4 支撑顶点（每条矩形边只接触凸包*一个顶点*，没有任何一条边与凸包的某条边重合——这正是反证 setup 假设的状态）； $\bm u = R-L$ （橙色箭头）和 $\bm v = T-B$ （紫色箭头）是反证 setup 里两个固定向量；左下角"指南针" $\hat n_\theta = (\cos\theta, \sin\theta)$ 、 $\hat n_\theta^\perp = (-\sin\theta, \cos\theta)$ 。}
\end{center}
**下一步问题**：在这张图上， $\text{width}(\theta)$ 等于哪个*内积*？ $\text{height}(\theta)$ 等于哪个*内积*？（即把宽和高分别写成两个向量的点积形式。）
> 🧑 **Note**:
**zzy (Me)**
我在想一共就两个向量，而且点积是符合交换率的吧，一共就两个向量点积、而且符合交换率的话，这哪能凑得出来两个内积啊？而且我也有一点忘记这个内积的定义了。
> 🤖 **Note**:
**Claude (Mentor)**
点积： $\bm a \cdot \bm b = a_1 b_1 + a_2 b_2 = |\bm a|\,|\bm b|\,\cos\angle(\bm a, \bm b)$ 。
向量数其实 **4 个**，不是 2 个：位移 $\bm u = R-L$ 、 $\bm v = T-B$ ，加上单位方向 $\hat n_\theta = (\cos\theta, \sin\theta)$ 、 $\hat n_\theta^\perp = (-\sin\theta, \cos\theta)$ 。"宽 / 高"各 = 一个*位移* $\cdot$ 一个*方向*，组合两对。
**重问**： $\text{width}(\theta)$ 配哪对？ $\text{height}(\theta)$ 配哪对？
> 🧑 **Note**:
**zzy (Me)**
我在想一个问题。我当然记得点积是指投影的长度，但记得这个投影的长度和 $B$ 肯定有关系，不止和 $A$ 有关系，和 $B$ 也有关系。但你的 $\hat n$ 是一个单位向量，但是你在阐述其几何意义的时候，怎么能够用单位向量呢？
或者我可以这么理解吗？我就把 $B$ 视为一个单位向量，虽然这个 $B$ 它可能长度不唯一，但是我可以把这个 $B$ 视为一个单位向量。是这个意思吗？
> 🤖 **Note**:
**Claude (Mentor)**
你的"定义 $|B|$ 为长度单位"是*换单位制*的描述：以 $|B|$ 为新单位时 $|B| = 1$ ，点积值 = 投影长度（按新单位测的数值）；换回绝对单位再乘 $|B|$ 。本质和"投影长度 $\times |B|$ "是同一件事，描述不同。
**原问题再问**： $\text{width}(\theta)$ 配哪对？ $\text{height}(\theta)$ 配哪对？
> 🧑 **Note**:
**zzy (Me)**
$\bm u \cdot \hat n_\theta$ 、 $\bm v \cdot \hat n_\theta^\perp$ 。
> 🤖 **Note**:
**Claude (Mentor)**
对。所以
$$
A(\theta) \;=\; (\bm u \cdot \hat n_\theta)(\bm v \cdot \hat n_\theta^\perp).
$$
这就是反证 setup 下 $A$ 的解析式（4 支撑 $L,R,T,B$ 固定 $\Rightarrow$ $\bm u, \bm v$ 固定；只有 $\theta$ 在变）。
**下一步**：把两个内积分量展开。设 $\bm u = (u_1, u_2)$ 、 $\bm v = (v_1, v_2)$ 。 $\bm u \cdot \hat n_\theta$ 用 $\cos\theta, \sin\theta$ 怎么写？ $\bm v \cdot \hat n_\theta^\perp$ 呢？
> 🧑 **Note**:
**zzy (Me)**
$\bm u \cdot \hat n_\theta = u_1 \cos\theta + u_2 \sin\theta$ ； $\bm v$ 同法展开 $\bm v \cdot \hat n_\theta^\perp = -v_1 \sin\theta + v_2 \cos\theta$ 。
> 🤖 **Note**:
**Claude (Mentor)**
对，所以
$$
A(\theta) \;=\; (u_1 \cos\theta + u_2 \sin\theta)\,(-v_1 \sin\theta + v_2 \cos\theta).
$$
**下一步**：把这个乘积**展开 + 化简**（提示：用 $\cos^2\theta = \tfrac{1+\cos 2\theta}{2}$ 、 $\sin^2\theta = \tfrac{1-\cos 2\theta}{2}$ 、 $\sin\theta\cos\theta = \tfrac{\sin 2\theta}{2}$ 把所有 $\theta$ 都升到 $2\theta$ ）。 $A(\theta)$ 化简后**只剩什么形式**？
> 🧑 **Note**:
**zzy (Me)**
设 $a = u_1\cos\theta,\ b = u_2\sin\theta,\ c = v_1\sin\theta,\ d = v_2\cos\theta$ ，则
\begin{align*}
A(\theta) & = (a+b)(-c+d) = -ca - cb + ad + bd
& = -u_1 v_1 \cos\theta\sin\theta - u_2 v_1 \sin^2\theta + u_1 v_2 \cos^2\theta + u_2 v_2 \sin\theta\cos\theta
& = (u_2 v_2 - u_1 v_1)\,\cos\theta\sin\theta - u_2 v_1 \cdot \tfrac{1-\cos 2\theta}{2} + u_1 v_2 \cdot \tfrac{1+\cos 2\theta}{2}.
\end{align*}
全部升到 $2\theta$ 后再合并："这有什么规律？"——展开后得到混着 $\cos 2\theta$ 、 $\sin 2\theta$ 、常数项的一坨，结构性的东西不显然。
> 🤖 **Note**:
**Claude (Mentor)**
把 /2 因子都收齐后：
$$
A(\theta) \;=\; \underbrace{\tfrac{u_1 v_2 - u_2 v_1}{2}}_{\displaystyle C_0} \;+\; \underbrace{\tfrac{u_2 v_1 + u_1 v_2}{2}}_{\displaystyle C_1}\cos 2\theta \;+\; \underbrace{\tfrac{u_2 v_2 - u_1 v_1}{2}}_{\displaystyle C_2}\sin 2\theta.
$$
**规律就在这里**： $C_0 + C_1 \cos 2\theta + C_2 \sin 2\theta$ 这种形式可以合并成单一正弦——
$$
A(\theta) \;=\; C_0 + R\sin(2\theta + \varphi), \quad R = \sqrt{C_1^2 + C_2^2}.
$$
——**周期为 $\pi$ 的简单正弦波**（频率 $2\theta$ 的简谐振荡），绕常数 $C_0$ 上下浮动，振幅 $R$ 。最初看起来杂乱（ $\cos\theta, \sin\theta, \cos^2\theta, \sin^2\theta$ 全混着），最后塌缩成"常数 + 一个正弦"这个最简结构。
**下一步**： $A(\theta)$ 既然是 $2\theta$ 的简单正弦波，它的**极小值取在 $\theta$ 为何值时**？（提示： $\sin(\cdot)$ 函数的极小在哪里？）
> 🧑 **Note**:
**zzy (Me)**
极小值在 $2\theta + \varphi = \tfrac{3\pi}{2} + 2k\pi$ 时取到。
> 🤖 **Note**:
**Claude (Mentor)**
对。等价地 $\sin(2\theta+\varphi) = -1$ ，所以 $A_{\min} = C_0 - R$ ，是**孤立的极小点**（只要 $R > 0$ ）。
**但等一下**——我们这一路推下来 $A(\theta) = C_0 + R\sin(2\theta+\varphi)$ 是在**反证 setup** 下：4 支撑 $L,R,T,B$ 固定 $\Rightarrow \bm u, \bm v$ 固定 $\Rightarrow$ 系数 $C_0, R, \varphi$ 固定。问题是：
**这个公式在 $\theta$ 取哪个范围内有效？** 换句话说， $\theta$ 转到**什么时候** $L,R,T,B$ 中的某一个会从一个 hull 顶点切换到下一个 hull 顶点？
> 🧑 **Note**:
**zzy (Me)**
这个比较难确定吧。
> 🤖 **Note**:
**Claude (Mentor)**
对——精确长度依赖 hull 几何（每次支撑切换发生在 hull 某个顶点处），不需要算。
反证其实只关心**一个性质**：smooth 区间 $I$ 是**开区间**——
- $\theta$ 在 $I$ **内部**时，4 支撑保持 $L,R,T,B$ （4 单点）；
- $\theta$ 触到 $I$ **端点**时，某个支撑切换 $\Leftrightarrow$ 矩形某条边和 hull 某条边**重合**（flush 状态）。
**反证假设** $\Leftrightarrow$ $\theta_0$ *不* flush $\Leftrightarrow$ $\theta_0$ 是开区间 $I$ 的**内点**。
**下一步**： $\theta_0$ 是 $A(\theta)$ 在开区间 $I$ 上的极小，且在 $I$ 的内点。这给出 $A$ 在 $\theta_0$ 处什么**一阶必要条件**？写出该等式（用 $C_1, C_2$ 或 $\bm u, \bm v$ 都行）。
> 🧑 **Note**:
**zzy (Me)**
什么叫一阶必要条件？？？？
> 🤖 **Note**:
**Claude (Mentor)**
术语澄清——**一阶必要条件**（first-order necessary condition，又叫 **费马引理**）：
*若* $f(x)$ 在**定义域内点** $x_0$ 处取局部极值（极大或极小），*且* $f$ 在 $x_0$ 处可导，*则*必有
$$
f'(x_0) = 0.
$$
**1D 直观**：极值点处函数曲线*切线水平*（左升右降 = 上凸极大；左降右升 = 下凸极小；切线斜率都是 0）。
**为什么强调"内点"**：在区间端点取极值时， $f'$ 不需要为 0（端点处只能往一边走，函数可以是单调的）。例： $f(x) = x$ 在 $[0,1]$ 上极小是 $x = 0$ ，但 $f'(0) = 1 \neq 0$ 。
**为什么是"必要"不是"充分"**： $f'(x_0) = 0$ 不一定保证 $x_0$ 是极值——也可能是**鞍点 / 拐点**（如 $f(x) = x^3$ 在 $x = 0$ ）。所以一阶条件只*筛掉了非极值的候选*，是否真极值还要看二阶导。
**回到题目**： $A(\theta)$ 是 $\theta$ 的光滑函数（sinusoid）， $\theta_0$ 是 $A$ 在*开*区间 $I$ *内部*的极小 $\Rightarrow$ 直接套用费马引理 $\Rightarrow A'(\theta_0) = 0$ 。
**回到原题**：把 $A(\theta) = C_0 + R\sin(2\theta+\varphi)$ 求导，写出 $A'(\theta_0) = 0$ 的具体形式。
> 🧑 **Note**:
**zzy (Me)**
继续吧，跳过引理证明部分，我们直接来看这个算法证明写。
> 🤖 **Note**:
**Claude (Mentor)**
好——**核心引理** 就此 buy-in：*覆盖凸包的最小面积矩形，至少有一条边与凸包某条边共线*。sinusoid + 费马引理那条严格化路径打住，先把算法跑通；要回填证明随时再开。
**已建立的产物保留作直觉**：4 支撑 $L,R,T,B$ 固定的平滑段内
$$
A(\theta) \;=\; C_0 + R\sin(2\theta + \varphi)
$$
是 $2\theta$ 的简单正弦——后面写算法时" $\theta$ 取段端点（也就是某支撑切线 flush 到凸包某条边）"这个结构感会直接复用。
## 第 3 步：算法骨架（暴力）
> 🤖 **Note**:
**Claude (Mentor)**
接受引理后，最直接的暴力算法**枚举什么**对象？
> 🧑 **Note**:
**zzy (Me)**
暴力枚举矩形的一条边和另外两个点呗。
> 🤖 **Note**:
**Claude (Mentor)**
方向对——枚举**一条凸包边** $e$ 当矩形"底边"（引理保证最优解里至少有这么一条 $e$ 存在），然后再确定剩下的支撑点。*准确计数是 3 个支撑点不是 2*：
- **底边方向**由 $e$ 给定，矩形**方向锁死**。设 $\hat n_e$ = 沿 $e$ 的单位向量， $\hat n_e^\perp$ = 垂直 $e$ 朝凸包内侧的单位向量。
- **T**（top）：凸包顶点中 $\hat n_e^\perp$ 投影最大的那个 $\Rightarrow$ 决定*高*。
- **L, R**（left, right）：凸包顶点中 $\hat n_e$ 投影最小 / 最大的两个 $\Rightarrow$ 共同决定*宽* = $R$ 投影 $-$ $L$ 投影。
所以是 1 条边 + 3 个点（ $T, L, R$ ）。 $L, R$ 在同一根投影轴上一次扫描就能同时拿到，可能这就是你脑子里把它们合并成"一个点"的来源。
**下一问**：固定 $e$ 之后，逐个扫描凸包 $h$ 个顶点找 $T, L, R$ 是 $O(h)$ ；外层枚举所有 $h$ 条凸包边。这个暴力的总复杂度是多少？
> 🧑 **Note**:
**zzy (Me)**
$O(n^2)$ 的这个级别吧。
> 🤖 **Note**:
**Claude (Mentor)**
对， $O(h^2)$ $\le$ $O(n^2)$ （凸包顶点数 $h \le n$ ）。 $n \le 5 \times 10^4 \Rightarrow n^2 = 2.5 \times 10^9$ ，2s 时限过不去，要再砍一个数量级。
**优化的入口观察**：把凸包边按 CCW 顺序记作 $e_0, e_1, …, e_{h-1}$ 。当外层枚举从 $e_i$ *推进*到 $e_{i+1}$ （底边方向连续微转一点点）时， $T, L, R$ 这三个支撑顶点**在凸包上是怎么动的**？（提示：从几何上想象底边逆时针偏转一个小角度，三条支撑切线随之偏转，各自的接触顶点会怎么变。）
> 🧑 **Note**:
**zzy (Me)**
我大概理解了，就是维护三个指针就可以解决这个问题。
> 🤖 **Note**:
**Claude (Mentor)**
对——这就是 **旋转卡壳（rotating calipers）**。结构性理由（不要跳）：
**单调性 / monotonicity**：底边方向 $\theta$ 沿 CCW 连续增加时， $T, L, R$ 三个支撑顶点**也只沿凸包 CCW 推进，从不回退**。原因——每个支撑顶点都是凸包上某个"投影极值"顶点（ $T$ = $\hat n_e^\perp$ 投影最大； $R$ = $\hat n_e$ 投影最大； $L$ = $\hat n_e$ 投影最小 = $-\hat n_e$ 投影最大），凸函数的极值点随方向 CCW 旋转只会 CCW 漂移（投影函数在凸包顶点序列上单峰）。
**摊还代价**：外层枚举凸包 $h$ 条边一圈，每个指针在凸包上最多走**一整圈** $h$ 步。三个指针合计 $O(h)$ 步，加外层 $O(h)$ 次面积更新 $\Rightarrow$ 卡壳部分 $\boldsymbol{O(h)}$ 摊还。
**全流程复杂度**：求凸包 $O(n\log n)$ + 旋转卡壳 $O(h) \le O(n)$ $\Rightarrow$ 总 $\boldsymbol{O(n\log n)}$ 。 $5\times 10^4 \log(5\times 10^4) \approx 8\times 10^5$ ，2s 绰绰有余。
**每个指针的推进判定**（具体写代码会用）：以 $T$ 为例——当前底边 $e_i$ = $H_i \to H_{i+1}$ ， $T$ 当前指 $H_t$ 。问" $T$ 该不该 advance 到 $H_{t+1}$ ？"等价于问" $H_{t+1}$ 离底边*更远*吗？"——用**叉积**表达：
$$
(H_{i+1} - H_i) \times (H_{t+1} - H_i) \;\ge\; (H_{i+1} - H_i) \times (H_t - H_i),
$$
也即 $(H_{i+1} - H_i) \times (H_{t+1} - H_t) \ge 0$ 。 $L, R$ 类似但用**点积**比较投影。
> 🧑 **Note**:
**zzy (Me)**
应该是需要维护 4 个指针吧？一个是边，另外 3 个是这个点，也就是代表这个切线。
> 🤖 **Note**:
**Claude (Mentor)**
对，更准确——**4 个指针**，分两类：
- **驱动指针**（for 循环）：底边索引 $i$ ，每轮 $i \to i+1$ 强制 advance 1 步，跑遍 $h$ 条凸包边作为"当前底边"候选。
- **跟随指针**（while 循环）： $T, L, R$ 三个支撑点，每轮在自己的 advance 条件不再满足前一直 \verb|++| (mod $h$ )。
**摊还修正**：4 个指针都沿凸包 CCW、各自最多走一整圈 $h$ 步，合计 $4h = O(h)$ 次操作 $\Rightarrow$ 卡壳部分仍然 $O(h)$ 。*驱动 / 跟随*的区别只是循环类型不同（确定步进 vs 条件步进），单调不回退这一点都满足。
## 第 4 步：实现
> 🤖 **Note**:
**Claude (Mentor)**
现在去把代码写了——`src/main.cpp`（或你已有的源文件），用旋转卡壳走一遍。流程：
- Andrew 求凸包，CCW 顺序输出 $h$ 个顶点。
- 初始化 $T, L, R$ 三指针：以 $e_0$ 为底边**独立扫一遍**找到三个初始位置。
- 外层 $i = 0 \to h-1$ 枚举底边 $e_i$ ；内层各自 `while` 推进指针到本轮的最优位置；算面积更新答案。
- 还原最优时的 4 个矩形顶点（*底边线* $\cap$ *左切线*、 $\cap$ *右切线*；同理上面）。
写完告诉我。
> 🧑 **Note**:
**zzy (Me)**
你直接写一个这个函数参考的实现吧，毕竟我们是在学习嘛。
> 🤖 **Note**:
**Claude (Mentor)**
好，我把参考实现写到 `src/P3187\_HNOI2007\_minimun\_rectangle\_cover.cpp` 里 `minimum\_rectangle\_cover`。
**相对原 stub 的两处签名调整**：
- *返回类型*：`array<DB, 5>` $\to$ `pair<DB, array<Point, 4>{}>`（5 个 `DB` 装不下面积 + 4 顶点 = 9 个数；`Point` 数组语义更清晰）。
- *Real 前置*：函数内部 `getintersect` 需要浮点除法，必须 `Real = DB`（模板顶部 `using Real = ll;` 改成 `using Real = DB;`）。本题输入也是浮点，本来就要切。
**三个写代码的细节**（mentor 推导没明说、写时会卡的）：
1. **初始化不能简单赋 0**。 $`up` = `r` = `l` = 0$ + 推进 `while` 严格 " $>$ " 时，`cross/dot` 都从 0 起步，不会被严格 " $>$ " 触发推进 $\Rightarrow$ 卡死在 0。要在外层 `for` 之前对 `edge = 0` 这条底边*独立扫一遍*找各自最优起点。
1. **推进条件用双线性化简**。` `$`cross`(e, A_{u+1} - A_e) >` cross`(e, A_u - A_e)$ ''减一下 $=$ $`cross`(e, A_{u+1} - A_u) > 0$ '' $=$ $`cross`(e, e\_of(`up`)) > 0$''。三个支撑点的判定都能写成 "*当前 polygon 边*$\cdot$ $e$"或"*当前 polygon 边*$\times$ $e$ "形式，比展开式干净一档。
1. **面积比较*不要*除 $\sqrt{|e|^2}$* *。直接乘出 $\text{Area} \cdot |e|^2 = `dot`(e, A_r - A_l) \cdot `cross`(e, A_{up} - A_e)$ 比较；除法和开根都只在最后输出最小答案前做一次。
**参考代码**（你自己在 cpp 里照着练）：
```cpp
// 最小矩形覆盖：返回 {面积, 4 个矩形顶点（以底边 BL 起、CCW）}
// 前置：Real = DB（reconstruct 走 getintersect 必须浮点）
pair<DB, array<Point, 4> > minimum_rectangle_cover(vector<Point> A) {
A = make_convex_hull(A);
int n = SZ(A);
auto e_of = [&](int i) { return A[(i + 1) % n] - A[i]; }; // 第 i 条凸包边的方向向量
// 初始化 up / r / l：在 edge = 0 这条底边上独立扫一遍，各自找最优起点。
// 不能直接 up = r = l = 0 — 推进 while 用严格 ">"，从 0 开始时 cross/dot 都是 0，会卡住。
int up = 0, r = 0, l = 0;
{
Point e0 = e_of(0);
for (int j = 1; j < n; ++j) {
if (cross(e0, A[j] - A[0]) > cross(e0, A[up] - A[0])) up = j;
if (dot (e0, A[j] - A[0]) > dot (e0, A[r] - A[0])) r = j;
if (dot (e0, A[j] - A[0]) < dot (e0, A[l] - A[0])) l = j;
}
}
DB best_area = numeric_limits<DB>::infinity();
int best_edge = 0, best_up = up, best_r = r, best_l = l;
// 4 指针：edge 是 for 驱动指针（确定步进），up/r/l 是 while 跟随指针（条件步进）
for (int edge = 0; edge < n; ++edge) {
Point e = e_of(edge);
// 推进条件用 "polygon edge × e" 化简：cross(e, A[up+1]-A[edge]) - cross(e, A[up]-A[edge]) = cross(e, e_of(up))
while (cross(e, e_of(up)) > 0) up = (up + 1) % n; // A[up+1] 离边更远 ⇔ cross(e, e_of(up)) > 0
while (dot (e, e_of(r)) > 0) r = (r + 1) % n; // A[r+1] 沿 e 投影更大
while (dot (e, e_of(l)) < 0) l = (l + 1) % n; // A[l+1] 沿 e 投影更小
// 面积 × |e|^2 = (宽 × |e|) × (高 × |e|)
// \_______/ \_______/
// dot(e, A[r]-A[l]) cross(e, A[up]-A[edge])
DB w_e = (DB) dot (e, A[r] - A[l]);
DB h_e = (DB) cross(e, A[up] - A[edge]);
DB area = w_e * h_e / (DB) e.norm();
if (area < best_area) {
best_area = area;
best_edge = edge; best_up = up; best_r = r; best_l = l;
}
}
// 还原 4 顶点 = 4 条切线两两相交（4 条线方向：底/顶 ∥ e；左/右 ∥ e^⊥）
Point e = e_of(best_edge);
Point e_perp(-e.y, e.x); // CCW 90° 旋转
Line bottom(A[best_edge], A[best_edge] + e);
Line top_ (A[best_up], A[best_up] + e);
Line right_(A[best_r], A[best_r] + e_perp);
Line left_ (A[best_l], A[best_l] + e_perp);
array<Point, 4> corners = {
getintersect(bottom, left_), // BL
getintersect(bottom, right_), // BR
getintersect(top_, right_), // TR
getintersect(top_, left_), // TL
};
return {best_area, corners};
}
```
**下一步**：把这份代码塞进 `Solve()` 里跑题面样例，AC 之后再做 stress test（\textsf{cyaron-stress} skill 的非均匀曲率形状）。
## 心路历程（mentor 走过的弯路）
- **第一次抛核心引理时被骂**: 直接说"接受这条引理后请描述暴力"，被怼"你代替我接受了？"。整段 setup（参数化 / 平滑段 / sinusoid / 核心断言 / 引理 / 收尾追问）一次性 dump 出去违反「mentor 推进只一步」硬约束，整段 `%` 行注释回滚作违规档底参考。
- **mentor 推进路线选错**: 想沿 sinusoid 反证 + 费马引理 $A'(\theta_0) = 0$ 走严格证明，推到内点极小子情况走不出矛盾——标准证明实际是构造性的（让矩形绕某支撑顶点旋转就能压缩面积）。本 session 选择跳过严格证明，buy-in 引理直接进算法。
- **指针数搞错**: mentor 数错支撑点数（说"另外 3 个"但 zzy 一开始报"另外 2 个"），后续 zzy 自己纠正成"4 个指针：边 i + T/L/R 三支撑"。
- **写参考实现位置错**: mentor 把参考实现写进了 cpp 主文件，被 zzy 怒怼"那个文件是我自己练的"。revert，改成 mentor.tex 内联 minted 块。
## AC 代码
> 进行中（cpp 还在敲）—— mentor 给的参考实现已嵌在上方"参考代码"段落，AC 后回来填提交链接和最终代码。
## 📎 附件
- **mentor.pdf**: 12 页完整带教对话录 PDF 版（xelatex 编译）。
[P3187 最小矩形覆盖 mentor 完整带教对话录（12 页 PDF）](https://media.znzryb.com/20260506-2dcc4807/P3187_mentor_226583eb.pdf)