凸包:QuickHull算法

对于凸包问题，QuickHull算法是一种常用的解决方法。它是一种递归的分治算法，用来计算给定点集的凸包。下面我简单介绍一下QuickHull算法的步骤：

1. 找出点集中x坐标最小和最大的两个点，将它们加入凸包的点集。

2. 将这两个点连成一条直线，将点集分成两部分：在直线上方的点和在直线下方的点。

3. 对于直线上方和下方的两个点集，递归地执行以下步骤：

- 在当前点集中，找出与连接两个端点的直线距离最远的点C，作为直线的支撑点。

- 将连接A、C和C、B的线段加入凸包的边集。

- 将点集根据直线AC和CB分成两部分，分别递归处理。

4. 递归结束条件：当某个点集为空或只有一个点时，结束递归。

5. 最终得到的凸包即为所有递归过程中加入的边和端点构成的闭合多边形。

QuickHull算法的时间复杂度为O(nlogn)，其中n为点集的大小。它具有较好的效率和稳定性，并且适用于高维空间的凸包计算。但需要注意的是，当点集中存在共线点时，QuickHull算法会出现问题，需要进行额外的处理。