Last updated 1 year ago
将多个点连接成一个多边形，就叫凸包。
从最左下的点开始
遍历所有点，取极角最小的点，作为下个遍历的点
遍历直到回到起点
将所有点按 x, y 排序
x, y
遍历两遍，分别构建上凸包和下凸包
以上凸包为例：
假设A为起点
遍历其他所有点，找出同 A 相连斜率最高的（假设为 X）
A
X
步进到 X，重复上述过程直到斜率变负
排序需要 O(NlgN)，第二步只需 O(2N)，比步进法高效
O(NlgN)
O(2N)
判断 AB 斜率的方法：
AB
如果点 C 在 AB 上方：
C
例题：
