凸包（Convex Hull）
计算几何 · Andrew 单调链 · O(n log n)
用橡皮筋套住一堆点
平面上撒了一堆点，凸包就是能把它们全都套住的最小凸多边形——想象拿一根橡皮筋绷开、松手让它收紧，最后贴住的那圈外围的点就是凸包的顶点，里面的点被包在内部。凸包是计算几何的地基：碰撞检测、最远点对、最小外接形状、路径规划的第一步，往往都从求凸包开始。
叉积：一次判断左转还是右转
核心工具是叉积。对三个点 O, A, B，cross(O,A,B) = (A−O)×(B−O) 的符号告诉你从 OA 到 OB 是往哪拐：大于 0 是左转（逆时针）、小于 0 是右转（顺时针）、等于 0 是三点共线。凸多边形（逆时针）的每个拐角都应该是左转；一旦出现右转，说明中间那个点是凹的，不该在凸包上。
单调链：下凸壳 + 上凸壳
Andrew 单调链先把所有点按 (x, y) 排序，然后分两趟。下凸壳从左到右扫描：维护一个栈，每加入一个点，就看栈顶两点到新点是不是非左转（叉积 ≤ 0）——是就弹栈（那个点是凹的），直到左转再把新点压入。上凸壳从右到左同样来一遍。两条链拼起来就是完整凸包，复杂度由排序决定，O(n log n)。
下面固定 7 个点。点「下一步」逐步看：琥珀是当前正在加入的点、红色是这一步因右转被弹出的点、灰色折线是当前的凸壳链。先构下凸壳、再构上凸壳，走到底两条链合成一圈绿色凸包多边形，中间的点 (3,3) 被留在里面。右侧代码随每一步同步高亮。
平面上 7 个点（已按 (x,y) 排序）。要用最紧的凸多边形套住它们——先从左到右构「下凸壳」，靠叉积判转向
为什么单调链这么优雅
cross(O,A,B) > 0 左转、< 0 右转、= 0 共线。排序：按
(x, y) 排好，保证扫描单调、每个点只进出栈常数次。弹栈：非左转（叉积 ≤ 0）就弹掉栈顶的凹点，栈里永远是凸的。
复杂度：排序
O(n log n) 主导，两趟扫描各 O(n)。 凸包只是计算几何的起点。有了它，旋转卡壳能在凸包上 O(n) 求出最远点对（直径）与最小外接矩形；Graham 扫描、礼品包裹（Jarvis 步进）是求凸包的其它经典思路；再往上还有半平面交、最近点对、扫描线等一整套「用叉积和排序处理几何」的方法。