凸包，多方法空间思维训练

https://www.luogu.com.cn/problem/solution/P2742

O(n³) 的算法

，凸包上的每一个线段，其余所有点都在线段同侧，枚举线段n²，枚举其余点n，一共n³

分治法/快速凸包算法，O（nlogn）

斜率逼近法

洛谷题解中作者说
其实都加上个基数不就没有无穷大了吗……

(其实这就是卷包裹法，复杂度为O(NH),其中N是全部的点数 H是最终在凸包上的点数)。Graham扫描法只取所有点对p1的斜率，后面的点充分利用该斜率的信息，并作某些处理，进行改进，以提高效率。这是由多到少，由多个到1个的方法，

Jarvis算法

https://blog.csdn.net/zhouzi2018/article/details/82177489
算法大体思想：形成凸包的构造函数是这样的，找到一条直线l过其中一点(记为A)并且所有其他点都在l的同侧(显然这样的直线一定可以找到)，则A必为凸包上的一点。让l以A为轴点向一个方向(比如：顺时针方向)不断旋转，直到l碰到除A以外的第一个点(记为B)。如果同时碰到多于一个点，则取与A点距离最大的。再次以B为轴点，向相同的方向的旋转l，重复上述过程，直到l回到A点。

Graham扫描法

Andrew算法

https://www.cnblogs.com/yjbjingcha/p/7255457.html