什么是二维凸包
假设墙上顶一组钉子，这些钉子的集合为X，我们用橡皮筋围住这些钉子，橡皮筋的形状就是凸包(来源于网络)。
向量的叉乘
对于两个向量pq⃗\vec{pq}pq和qr⃗\vec{qr}qr
- 如果pq⃗\vec{pq}pq和qr⃗\vec{qr}qr的叉积结果大于0，说明两者之间小于180度(以pq⃗\vec{pq}pq方向为极轴，逆时针追踪qr⃗\vec{qr}qr)，说明r在pq⃗\vec{pq}pq的左边
- 如果pq⃗\vec{pq}pq和qr⃗\vec{qr}qr的叉积结果小于0，说明两者之间大于180度(以pq⃗\vec{pq}pq方向为极轴，逆时针追踪qr⃗\vec{qr}qr)，说明r在pq⃗\vec{pq}pq的右边
- 如果pq⃗\vec{pq}pq和qr⃗\vec{qr}qr的叉积结果等于0，说明p,q,r三点在同一条线上
Gragam扫描法
算法流程：
- 找到一个一定在凸包中的初始点，比如最左下的点。
- 按拟时针逐个加入可能在凸包中的点。做法就是先把剩下的点集按照相对初始点的极角排序，如果极角相同，则按距离顺序近的在前。
- 我们从排序好的有序点中将前两个点放入结果栈中。然后从第三个点开始遍历剩余的有序点。假设当前点是a，上一个点是a-1，上上一个点是a-2。我们通过叉乘判断a−2，a−1⃗\vec{a-2，a-1}a−2，a−1和a−1，a⃗\vec{a-1，a}a−1，a的结果，如果叉乘结果小于等于0，说明a点没错。如果叉乘结果大于0，说明a-1就有问题，则把a-1点从结果栈中吐出，再判断新a-1点与a-2和a的叉乘结果，知道结果小于等于0.
对于叉乘结果=0的特殊情况，那我们根据远近依次排序
详细解释可以看参考1、参考2。
