前言
题目链接
首先说明一下，这题题面有个地方不太严谨：题意要求求凸包直径，然而当 \(n=2\) 时凸包并不存在，此时直径也应该不存在。所以应该是求平面中最远的点对的距离。
旋转卡（qia）壳可以用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离等。
这里就不过多赘述了，仅介绍两种不同的方案 —— 三角形面积比较与坐标系旋转，需要学习旋转卡壳正确性、原理的同学请移步这两位大佬的 blog cjyyb 和 xdruid。
方案一为三角形面积比较，是常规方案，在某些题里较麻烦（比如 P3187 [HNOI2007] 最小矩形覆盖 ）；方案二坐标系旋转貌似没有那么常见，但在大多数凸包题里更加方便与实用。
注意事项 —— 从零或一开始存储凸包中的点
在提供方案前我先多嘴几句注意事项，个人认为挺重要的（\(\sout{因为踩坑了}\)）。
- 注意：你的 \(stk\) 从 \(0\) 和从 \(1\) 开始的实现方式是不同的。（\(stk\) 数组中存储凸包中的点）
主要在于取模方式：如果从 \(0\) 开始，须使用 \((j+1)\mod tp\)；如果从 \(1\) 开始，则须使用 \(j \mod tp + 1\)。
- 原因：
- 对于从 \(0\) 开始，先加后模可以取到 \(0\)，而先模后加无法取到 \(0\)。
解释：当 \(j=tp-1\) 时，\((j+1)\mod tp=0\)，取到了 \(0\)。然而 \(j\mod tp+1=tp\)，由于从 \(0\) 开始存储，所以 \(tp\) 是一个空位，并且 \(tp\mod tp+1=1\)，故无法取到 \(0\)。
- 同理，对于从 \(1\) 开始，先加后模取到了 \(0\)，没有取到 \(tp\)，然而 \(0\) 是个空位，所以需要先模后加。
具体的代码差别可以看方案一中的两种代码实现
方案一：三角形面积比较
实现原理
众所周知，叉积可以求平行四边形的面积，而三角形面积为平行四边形面积的一半，并且它们同底等高。所以比较三角形的高等价于比较平行四边形的面积大小，即比较叉积大小。
实现
从零开始
:::success[从零开始]
[code]void Andrew(){ sort(p,p+n); n=unique(p,p+n)-p; int lst=1; for(int i=0;ilst&&Cross(stk[tp-2],stk[tp-1],p)=0;i--){ while(tp>lst&&Cross(stk[tp-2],stk[tp-1],p) |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
