核心概述：在已给定的逆时针凸包上用旋转卡壳在线扫描，O(n) 找到最远点对（凸包直径）。
Description: Returns the two points with max distance on a convex hull (ccw, no duplicate/collinear points). Time: O(n) Status: stress-tested, tested on kattis:roberthood
展开阐述：
-
定义与背景
- 凸包直径：凸多边形上两点间的最大欧氏距离，亦称最远点对。常用于形状尺度估计、最小包围矩形的中间过程。
- 前提：输入为凸包顶点序列，逆时针，且无重复/共线中间点。若尚未构造凸包，先用025-几何-凸包。
-
接口/输入输出（据实现）
- array<P,2> hullDiameter(vector
S)，P=Point
。 - 输出为两端点的数组 {a, b}；内部以距离平方比较，避免反复开方。
- array<P,2> hullDiameter(vector
-
核心算法流程（Rotating Calipers）
- 初始化：令 n=|S|，若 n<2 直接返回；通常从 i=0, j=1 开始。
- 对每个 i（0..n-1）：
- 沿对踵点推进 j，使得距离 |S[i]-S[j]| 单调不减。
- 推进判据：当 (S[(j+1)%n] - S[j]).cross(S[(i+1)%n] - S[i]) > 0 时，j = (j+1)%n。
- 更新最优：以 dist2 比较并记录最远点对。
- 线性复杂度来源：i、j 各至多环绕一圈。
-
复杂度与边界条件
- 复杂度：双指针单调推进，总体 O(n)。
- 小规模与退化：n=1 返回该点与自身（实现可特殊处理）；n=2 直接返回两端。
- 共线：若输入存在共线中间点会影响推进次数与正确性，需保证输入已去除中间点。
-
实现细节与常见坑
- 比较使用 dist2（ll 计算可能溢出，必要时用内建 128 位）。
- 判据使用 >= 或 > 的取舍会影响 j 的停留与推进，需与实现保持一致以避免漏解。
- 注意索引取模，避免数组越界。
-
变体与扩展
- 同步计算最小包围矩形：在卡壳过程中维护与边平行的外接矩形，输出面积最小者。
- 三维最远点对：可通过旋转卡壳推广但实现复杂度高。
-
正确性要点与不变式
- 对踵点性质保证每条支撑线至多对应一个最远方向，双指针总推进次数线性。
- 凸性与 ccw 顺序是旋转卡壳正确性的关键前提。
-
对比与取舍
- 与暴力 O(n^2) 比：显著加速。
- 与 KD 树等结构：全局最远点对在凸包上，先取025-几何-凸包再卡壳是标准方案。