旋转卡壳

旋转卡壳： 对于一类问题，要求平面上所有点对之间距离最远的点对，这类问题称为平面最远点对问题。而旋转卡壳就是一种用来求平面最远点对的思想。

旋转卡壳的思路：

首先从直觉上想，距离最远的两个点一定是在凸包上的两个点。

假设最远点对 $(a, b)$ 不在凸包上，那么一定在凸包内部，此时我们可以将最远点对之间的线段向两边延长与凸包的边相交，此时直线和凸包上的两个交点之间的距离一定 $>(a,b)$ 之间的距离，然后我们将这条直线绕着其中一个交点进行旋转，此时直线绕着顺时针或逆时针将另一个交点旋转到凸包的顶点上，此时一定存在一个方向是能让两个交点之间的距离变大的，同理我们再绕着这个交点旋转，一样可以将另一个交点旋转到凸包的顶点上，且交点之间的距离会变大，因此对于任意一个凸包内的点对我们都能构造出一个比 $(a,b)$ 距离更远且在凸包顶点上的点对。由此得出距离最远的点对一定在凸包上。

到此我们就将答案缩小到凸包上，我们只需要在凸包上的点对中找出最远点对。这里就可以用旋转卡壳的思想在凸包上找最远点对。

我们准备两条方向相反的平行线，一条从凸包的上面向下平移，一条从凸包的下面向上平移，然后两条平行线会分别被凸包的某一个点卡住，然后我们将两条平行线同时绕着凸包逆时针旋转 $360^。$，在旋转的过程中两条平行线之间的距离的最大值就是最远点对之间的距离。

证明也比较容易证明，假设最远点对是 $(a,b)$，那么当两条平行线和 $ab$ 垂直时，此时两条平行线会刚好通过 $a,b$ 两点夹住整个凸包，此时平行线之间的距离就是 $a,b$ 之间的距离。

然后我们需要考虑如何枚举所有情况，因此我们这里枚举的是平行线的角度，而角度是有无穷多种取值的，因此我们枚举的时候需要枚举一些离散值，使得枚举的数量不会太大。我们考虑所有能卡住两条平行线的点对，这种点对被称为对踵点，对踵点一定是成对出现的。当平行线旋转的过程中，对踵点是不断发生变化的。

然后可以发现所有的对踵点之间距离的最大值，就是最远点对的距离。这一点也很直观，模拟一下平行线旋转的过程就能很容易看出。

因此我们只需要找出所有对踵点对，找出所有对踵点对之间距离的最大值，就是答案。

由于我们的目标只是找出所有的对踵点对，因此我们枚举角度的时候不需要枚举所有的角度，只需要枚举对踵点发生变化的角度。而只有其中一条平行线和某一条边 $ab$ 平行时，对踵点才会发生变化，假设此时另一条平行线和凸包的交点是 $p$，那么此时对踵点对就从 $(p,a)$ 变成了 $(p,b)$，我们只需要找出所有这种对踵点对变化的时刻，就能找出所有的对踵点对。

而所有对踵点对变化的时刻，很容易可以看出就是某一条平行线和某一条边重合的时刻，因此我们可以直接枚举每条边，对于每条边 $ab$，我们将他看作其中一条平行线，那么此时另一条平行线和凸包的交点就应该是距离 $ab$ 最远的一个点，那么此时对于每条边我们都可以找到发生变化前的对踵点对和发生变化后的对踵点对，这里为了方便，我们对于每条边，不用分清楚 $a$ 和 $b$ 哪个点是变化之前的对踵点，哪个点是变化之后的对踵点，由于它们都是某个时刻的对踵点，因此我们可以同时拿 $(p,a)$ 和 $(p,b)$ 来更新答案，这样枚举完所有边，我们就能找到所有对踵点对，就能得到最终答案。

那么现在我们就是要对于每条边，找到距离它最远的一个点，由于这是一个凸包，因此对于凸包上每个点到当前边的距离一定是先增加再减小，而我们此时就是要找到最大的一个位置，相当于是一个顶峰。由于这个点此时也是被一条平行线卡住的，因此如果我们逆时针枚举每条边，那么对应的另一条平行线卡住的点也一定只会沿着逆时针方向单调向后走，所以我们就可以用双指针算法来找到距离每条边最远的点。

假设距离当前枚举的边最远的点是 $p$，则当枚举到下一条边时，我们只需要看一下 $p$ 和逆时针的下一个点 $q$，哪个点距离这条边更远，如果 $p$ 更远，则最远点不变，如果 $q$ 更远，则此时最远点应该从 $p$ 变成 $q$，然后继续判断 $q$ 和逆时针的下一个点哪个更远，直到找到一个点距离这条边的距离，比下一个点更远时，我们就找到了对于这条边来说是顶峰的一个点。

那么对于一条边 $ab$，我们如何判断 $p$ 和 $q$ 哪一个距离它更远呢，这里可以用叉积来判断，对于三角形 $abp$ 和三角形 $abq$ 来说，他们的底边都是 $ab$，高分别是 $p$ 和 $ab$ 的距离以及 $q$ 和 $ab$ 的距离，那么此时 $abp$ 和 $abq$ 哪个三角形的面积更大，就直接决定了 $p$ 和 $q$ 哪个点距离 $ab$ 更远。而求三角形的面积我们就可以用叉积来求。

综上所述，就是旋转卡壳的全部思路。然后枚举所有对踵点是 $O(n)$ 的，因此旋转卡壳的瓶颈在于求凸包，整个的时间复杂度就是 $O(nlogn)$。

注意，为了方便，这里求凸包的时候最好逆时针方向存储所有边，这样在枚举每条边的时候，求出来的三角形的面积都是正的，更符合直觉，所以这里求凸包的时候应该先求下凸包，再求上凸包。并且如果存在多点共线的情况，此时三角形的面积都是 $0$，我们没法通过叉乘找出距离最远的点，因此我们还需要特判多点共线的情况，我们可以在求凸包时不保留点在直线上的情况，这样如果最终栈中只有 $1$ 个元素，说明是多点共线的情况，最左边的点和最右边的点的距离就是答案（如果多点共线，那么求完凸包后栈中只有两个元素且都是起点，去掉末尾多余的起点后就只有一个元素了）。