核心概述：用 Andrew 单调链算法在 O(n log n) 时间构建点集凸包（逆时针顺序），排除边上共线中间点。
Returns a vector of the points of the convex hull in counter-clockwise order. Points on the edge of the hull between two other points are not considered part of the hull. Time: O(n \log n) Status: stress-tested, tested with kattis:convexhull
展开阐述：
-
定义与背景
- 凸包：包含所有点的最小凸多边形，其顶点来自输入点集的极点。
- 典型场景：最远点对（028-几何-凸包直径）、点集可视边界、碰撞外框、GIS 边界估计等。
- 接口（据实现）：
- vector
convexHull(vector
pts)，P=Point
；若 sz(pts) ≤ 1，直返 pts。
- vector
-
核心算法流程（Andrew Monotone Chain）
- 排序：按 x 再 y 的字典序排序点集。
- 构建下链：依次扫描，将当前点 p 推入前，用 cross(h[t-2], h[t-1], p) ≤ 0 时弹栈，确保“左转”保持凸性。
- 构建上链：对排序后的点序反向重复上述过程。
- 合并：拼接上下链，去掉最后一个重复端点；若 t2 且 h[0]h[1]，减一避免重复。
- 输出：逆时针顺序顶点，排除边上共线中间点（通过 ≤0 判定）。
-
复杂度与边界条件
- 复杂度：排序 O(n log n)，扫描 O(n)，总计 O(n log n)。
- 多重点与共线：
- 若存在重复点，排序后相邻，弹栈规则不受影响；输出不含重复。
- 共线点置于边上时被排除（严格凸包顶点），若需保留边上所有点，将判定改为 <0。
- 全部共线：结果包含两端点（或实现细节下的最小端点集）；按具体实现可能仅返回两个端点。
- 坐标范围：P=Point
，叉积可能超 64 位，必要时以内置 128 位计算。
-
实现细节与常见坑
- 方向与顺序：输出为 ccw；若需 cw，可反转输出。
- 比较运算：排序与去重需一致的比较器；若要先 unique 去重，当心稳定性。
- 判定边界：cross 判定采用 ≤0 使得共线中点被弹出；修改为 <0 可保留共线点。
- 小规模：n ≤ 1 直接返回；n=2 返回两个点（按实现可能去重）。
-
变体与扩展
- 维护动态凸包：需要复杂数据结构（不在本实现范围）。
- 3D 凸包：见017-几何-三维凸包。
- 半平面交获取凸多边形：与凸包问题互补。
-
正确性要点与不变式
- 栈内顶点始终保持凸性与单调性；每次仅在右转/共线时弹出破坏凸性的点。
- 上下链覆盖全局极点，拼接后为完整凸边界。
-
对比与取舍
- 与 Graham 扫描法相比：实现更简洁，排序后线性扫描；二者复杂度相当。
- Jarvis 行走（礼物包装）：在极端情况下 O(nh)，当 h（凸包顶点数）很小时可能更优。