已知点集P的凸包CH(P)含4个顶点，如何在O(n)时间内求解

已知点集P的凸包恰好包含4个顶点，且所有点的x、y坐标互不相同，我们可以利用极值点必在凸包上的特性，在O(n)时间内直接找出所有凸包顶点：

步骤1：一次遍历找出四个关键极值点 #

遍历点集一次，记录以下四个唯一的点：

• A：x坐标最小的点（因x坐标全唯一，仅一个）
• B：x坐标最大的点
• C：y坐标最小的点
• D：y坐标最大的点

由于凸包恰好有4个顶点，这四个点必然是凸包的全部顶点（若有任意两个极值点重合，凸包顶点数会少于4，与题设矛盾）。

步骤2：按凸包顺序排列四个点（可选） #

如果需要按逆时针/顺时针顺序输出凸包顶点，可通过叉积快速判断点的相对位置：

1. 以x最小的点A为基准，计算B、C、D相对于A的向量叉积，区分左右方向。
2. 比如，计算cross(AB, AC)：
   • 若结果为正，说明C在AB的逆时针方向；若为负则在顺时针方向。
3. 以此类推，将四个点按凸包的环序排列，这一步是O(1)操作，不影响整体时间复杂度。

为什么这个方法是O(n)？ #

仅需一次线性遍历即可找出四个极值点，后续排序四个点是常数时间操作，整体时间复杂度为O(n)，完全符合要求。

内容的提问来源于stack exchange，提问作者Biplab Roy