二维凸包的相关概念

二维凸包： 在二维平面上有若干个点，用一个线圈包住所有的点，然后将线圈缩小，最终这个线圈将被最外围的一圈点勒住，此时的线圈是一个凸多边形的形状，这就是这些点的二维凸包。

凸包一定是围住这些点的周长最小的一个多边形。

求凸包有两个常用的算法，$Graham$ 和 $Andrew$，两个算法效果是一样的，没有很大的区别，但是 $Graham$ 算法中需要用到角度，所以我们就会涉及到一些反三角函数，反三角函数在精度和效率上都会相对低一点，因此相对更推荐 $Andrew$ 算法，当然 $Graham$ 在精度和效率上也只是低一点点，也是可以用的。

Andrew 算法的原理：

先将所有点按照横纵坐标来排序，这是一个双关键字排序，以横坐标为第一关键字，纵坐标为第二关键字。

我们将凸包分成上半部分和下半部分，分别来求。我们从左到右枚举所有点去求上半部分凸包，然后再从右到左枚举所有点去求下半部分凸包。

对于上半部分，我们从左到右枚举每个点，枚举的过程中我们用一个栈来维护当前的凸包。枚举每个点 $i$，当栈中元素个数 $\leq 2$ 的时候，直接将当前点 $i$ 加入栈中。如果栈中元素个数 $> 2$，那么此时我们考虑在什么情况下需要对当前凸包进行修改，由于我们从左到右枚举，所以 $i$ 一定在当前凸包的右边，我们如果将凸包的最右边的一条边看作一个从左向右的向量，那么此时如果 $i$ 在该向量的右侧，则按照凸包的形状来考虑，该向量不用被删去，我们可以直接将 $i$ 加入栈中。如果 $i$ 在该向量的左侧，则此时我们应该将该向量删去，在考虑将 $i$ 加入栈中，如果我们将该向量删去后，将此时凸包的最右边的边再看作一个向量，如果 $i$ 还在向量的左侧，我们还应该将向量删去，直到 $i$ 在向量的右侧位置，我们将 $i$ 加入栈中，以此类推继续枚举每个点。

注意还有一个特殊情况，就是 $i$ 可能在向量上，此时是否要将向量删去，取决于题目要求中是否要求你将凸包边界上的所有点都保留下来，如果要保留，则不用删掉，如果不要保留，则需要删掉。

当我们从左到右枚举完所有的点，我们就将上半部分的凸包找出来了，然后我们再从右往左将下半部分的凸包找出来，从右往左枚举的过程和上面的思路是一样的，如果当前点在向量的右侧，我们就直接将点加入，如果当前点在向量的左侧，我们就将向量删去，直到当前点在向量的右侧，我们再将点加入，以此类推。

然后注意，我们求完上凸包后，我们需要将上凸包中的点进行标记，以免被重复用到下凸包中，由于最终我们是要将上凸包和下凸包合并的，因此我们只需要用一个栈，存储完上凸包后再继续存储下凸包即可，但是由于上凸包是从第一个点开始的，那么我们最终要想将上、下凸包连成一整个凸包，因此我们在枚举下凸包之前应该将第一个点的标记删掉，这样下凸包最后会再枚举一次第一个点，就能将上、下凸包连起来了。

那么我们如何判断一个点 $p$ 是否在向量 $\vec{uv}$ 的左侧，可以用叉积判断，如果 $\vec{uv} \times \vec{up} > 0$，说明 $p$ 在 $\vec{uv}$ 的左侧，$<0$ 说明在右侧，$=0$ 说明在向量上。