> For the complete documentation index, see [llms.txt](https://wtifs.gitbook.io/diva-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wtifs.gitbook.io/diva-notes/algorithm/tu-bao.md).

# 凸包

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

## 步进法

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

![img](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-0f608d099db77c954fc9937ee335f5b60b9ad4de%2Fv2-00262801fbba6191268d0be4a5cfb774_1440w.jpg?alt=media)

## 单调链算法

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) \\
$$

![image](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-ef89259c44ed1d600e56ea068b70778b5e6ef7aa%2F4ae30ac4-6e6f-47fa-9528-7f725735cbbf_1630671725.490843.png?alt=media)

例题：[587. Erect the Fence](https://leetcode.com/problems/erect-the-fence/)