​点集的直径是平面最远点对的距离。直径一定可以由其凸包上的两个顶点取得，因此原始点集应先求凸包。

输入约定

设凸包顶点为 $p_0,p_1,\dots ,p_{n-1}$，下标按模 $n$ 计算。旋转卡壳的通用流程要求：

• 删除重复坐标、末尾重复的首点以及由此产生的零长度边；
• 顶点统一按逆时针顺序排列；
• 删除凸包边上的共线中间点。若业务需要保留这些点，可以在规范化副本上执行本文流程，再映射回原下标；不能直接套用下述严格推进规则；
• 空集的直径没有定义；$n=1$ 时直径为 $0$，$n=2$ 或全体点共线时直接计算线段两端的距离，不套用一般卡壳流程。

若输入是 $N$ 个未排序点，求凸包通常需要 $O(N\log N)$；下文的线性复杂度只计算已有规范凸包后的卡壳过程。整数坐标实现还应根据坐标范围为叉积和距离平方选择足够宽的中间类型。

旋转卡壳求直径

​用两条平行支撑线绕凸包旋转，它们与凸包的接触点或接触边构成对踵对。

​对于边 $p_i{p}_{i+1}$，定义二倍有向面积

$$A(i,j)=\mathrm{cross}(p_{i+1}-p_i,p_j-p_i)$$

​在逆时针凸包上，固定 $i$ 后，$A(i,j)$ 随 $j$ 沿凸包循环呈单峰变化，但最大值可能形成平台。边 $p_i{p}_{i+1}$ 逆时针移动时，使面积最大的顶点下标 $j$ 也只会沿逆时针方向移动，因此可以使用双指针。

算法流程

1. 对第一条边从 $j=1$ 开始，仅在 $A(0,j+1)>A(0,j)$ 时推进，使 $j$ 停在最大值平台的第一个点。
2. 依次枚举边 $p_i{p}_{i+1}$。当 $A(i,j+1)>A(i,j)$ 时向后移动 $j$，直到面积不再严格增大。
3. 使用 $p_j$ 分别与当前边的两个端点 $p_i,p_{i+1}$ 更新直径。
4. 若 $A(i,j+1)=A(i,j)$，说明 $p_j,p_{j+1}$ 位于同一个对踵平台，还要使用 $p_{j+1}$ 与当前边的两个端点更新答案。输入已经删除共线中间点时，最大值平台至多由一条支撑边的这两个端点构成。
5. 继续枚举下一条边，且不重置 $j$。

​也可以在面积相等时继续移动指针，但必须在每次移动前后更新平台上的候选，并给循环设置单圈或步数边界；不能使用“相等就一直移动，循环结束后只检查最后一个点”的流程。若不删除共线中间点，则需要能越过非最大平坦段、单调维护整个平台并重新证明复杂度的广义实现。对于同一条边，点到直线的距离只相差一个固定的边长分母，所以可以直接比较 $A(i,j)$，无需开方。文中的大小与相等比较默认使用精确几何谓词；浮点实现需要采用统一且与数据尺度匹配的容差策略。

​边指针枚举 $n$ 条边；对踵指针使用只增不减的展开下标，访问顶点时再对 $n$ 取模，并设置明确的推进步数上界。初始化和完整枚举期间该指针总共只推进 $O(n)$ 次，因此时间复杂度为 $O(n)$。

应用

两个凸多边形间的最大、最小距离

​设两个非空凸多边形为 $P,Q$，并将它们视为包含内部和边界的闭凸集。定义差多边形

$$D=P+(-Q)=\{p-q\mid p\in P,q\in Q\}$$

​任意 $z\in D$ 都对应一对点之差，所以

$$d_{max}(P,Q)=\underset{z\in D}{max}\Vert z\Vert ,d_{min}(P,Q)=\underset{z\in D}{min}\Vert z\Vert$$

• 最大距离可以在 $D$ 的某个顶点取得，构造 $D$ 后扫描所有顶点即可；
• 求最小距离时，若原点位于 $D$ 的内部或边界上，则 $P\cap Q\ne \varnothing$，包括相交、相切或一个多边形包含另一个的情况，答案为 $0$；否则最近点可能位于 $D$ 的边内部，应扫描所有边并计算原点到线段的距离，不能只扫描顶点。

​构造 $-Q$ 后仍需将其按与 $P$ 相同的极角断点重新规范化，再按极角归并两组边向量；方向相同的边向量应相加，并同时推进两个指针。两个输入凸包已经去重、同向有序并规范起点时，构造 $D$ 及上述扫描可以在 $O(|P|+|Q|)$ 时间内完成；点或线段等退化凸包需单独处理。

​最小距离也可以直接对两个凸包做专门的线性卡壳：必须先完整处理边相交、相切和包含，不相交时在相应事件中计算点到线段或线段到线段的距离，并处理平行边同时推进的情况。这不是求直径的“最大点到边面积”流程，不能直接复用上面的更新式。

凸多边形的最小面积、最小周长外接矩形

​最小面积或最小周长外接矩形一定存在一条支撑边与凸包的某条边共线。枚举每条凸包边作为基准方向时，除当前边外，还需维护三个单调移动的支撑点：法向距离最大的点，以及沿边方向投影最小、最大的两个点。由这些投影可以得到当前外接矩形的长和宽，并更新面积或周长。

​各支撑方向出现相等投影时同样需要规定平台的推进方式。规范凸包上的所有指针总共只前进 $O(n)$ 次，因此卡壳部分的时间复杂度为 $O(n)$；若对每条边重新扫描所有顶点，则会退化为 $O(n^2)$。单点和线段的外接矩形需按题目是否允许退化矩形单独约定。