本系列文章力求以简洁易懂的文字介绍计算几何中的基本概念，使读者快速入门，故不追求难度和深度，仅起到抛砖引玉的作用。

       看到这个算法的时候第一反应是脑子卡壳叭，尤其是我们在做这道家喻户晓的模板题的时候：

             [USACO03FALL] Beauty Contest G /【模板】旋转卡壳 - 洛谷  

        我们将一个多边形上任意两点间的距离的最大值定义为多边形的直径，那么我们如果直接枚举直径所在的两点， 显然太慢了。那么有一个O(n)的算法：旋转卡壳，计算时就像一对平行卡壳卡住凸包旋转而得名，可以说这个名字取得非常的形象，那么我们来看一下这道题目的思路历程：

          在二维平面上给定n个点，求距离最远的两个点之间的距离是多少？

      看到这道题，大部分同学第一反应肯定是暴力——暴力枚举所有点对，然后求出最远的那一对相距的距离。这种方法当然没错，可是复杂度已经达到了O(n^2)，当n是50000,100000，甚至1000000时，暴力就显得苍白无力。

      这时我们进一步思考，这个最远点对一定会出现在这些点集的凸包上，所以在这里我们在凸包上，使用复杂度低至O(n)的旋转卡壳算法进行求解。

     什么是平行卡壳？非常形象的说法就是卡住凸包的一对平行线，然后旋转卡壳就是让这对平行线旋转起来：

    在凸包上，被一对平行卡壳正好卡住的对应点对称为对踵点；可以证明对踵点的个数不超过3n/2个也就是说对踵点的个数是O(n)的，对踵点的个数也是我们下面解决问题时间复杂度的保证。那么我们来看看旋转卡壳中平行卡壳卡凸包的时候会出现的情况，基本上就是如下两种：

      1.卡住一个点和一条边：

        2.卡住两顶角的两个点：

       由于在处理过程中，卡壳卡住两个点的情况不好处理，所以一般我们都是去关注第一种情况。在这种情况下我们发现，一个对踵点到对应边之间的距离比其他点要大。也就是说，一个对踵点和对应边所形成的三角形的面积是最大的，所以我们可以使用叉积的第二种用法——求三角形面积来求解对踵点。又是叉积~：

        经过比对我们发现，对踵点对距离中的最大值，就是在这个二维平面内两点距离的最大值，总的时间复杂度为O(n)。

      1.旋转卡壳算法是建立在二维凸包上的，所以我们先需要对点集求出二维凸包，在之前的文章中已经细讲过了GrahamScan算法。

       有关二维凸包的求解：

             计算几何系列 ——— 结构之美（三角形四心一点，多边形&凸包算法）-CSDN博客

      2.现在我们需要考虑，如何得到距离每条对应边的的最远点呢?稍加分析,我们可以发现,我们可以把点到直线的距离化解为三角形的面积，再运用叉积进行比较。

        同时，凸包上的点依次与对应边产生的距离成单峰函数,面积上升到最高点后，又会下降。(具体证明可以从凸包定义入手用反证法解决)   

     因此，在求对踵点的过程时，我们采用的是直接枚举，并且利用单峰函数的性质，我们枚举到当下一个点的距离比上一个小的时候我们就停止枚举。  而且随着对应边的旋转，最远点也只会顺着这个方向旋转~，因此，我们可以从上一次的对踵点开始继续寻找这一次的。

     ps:  由于内层while循环的执行次数取决于j增加次数 j最多增加O(n)次，所以求出所有对踵点的时间复杂度为O(n)，对踵点三角形面积求解：