凸包.md

二维凸包 (2D Convex Hull)

将多个点连接成一个多边形，就叫凸包。

步进法

1. 从最左下的点开始
2. 遍历所有点，取极角最小的点，作为下个遍历的点
3. 遍历直到回到起点

单调链算法

1. 将所有点按 x, y 排序
2. 遍历两遍，分别构建上凸包和下凸包
   1. 以上凸包为例：
      1. 假设A为起点
      2. 遍历其他所有点，找出同 A 相连斜率最高的（假设为 X）
      3. 步进到 X，重复上述过程直到斜率变负
3. 排序需要 O(NlgN)，第二步只需 O(2N)，比步进法高效

判断 AB 斜率的方法： $$ Kab = (yb - ya) / (xb - xa) $$ 如果点 C 在 AB 上方： $$ (yc - ya) / (xc - xa) > (yb - ya) / (xb - xa) \ => (yc - ya) * (xb - xa) > (yb - ya) * (xc - xa) \ $$

例题：587. Erect the Fence