凸包

凸包

定义

平面上能包含所有给定点的最小凸多边形称为 凸包。

Andrew 算法

按 $x$ 为第一关键字、$y$ 为第二关键字排序，分别求上下凸壳，$O(n\log n)$。

struct Point {
  double x, y;
  Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
  double cross(const Point &p) const { return x * p.y - y * p.x; }
  bool operator<(const Point &p) const { return x == p.x ? y < p.y : x < p.x; }
};
 
vector<Point> andrew(vector<Point> p) {
  sort(p.begin(), p.end());
  vector<Point> stk;
  for (int i = 0; i < (int)p.size(); ++i) {
    while (stk.size() > 1 && (stk.back() - stk[stk.size() - 2]).cross(p[i] - stk.back()) <= 0)
      stk.pop_back();
    stk.push_back(p[i]);
  }
  int m = stk.size();
  for (int i = (int)p.size() - 2; i >= 0; --i) {
    while (stk.size() > m && (stk.back() - stk[stk.size() - 2]).cross(p[i] - stk.back()) <= 0)
      stk.pop_back();
    stk.push_back(p[i]);
  }
  stk.pop_back();
  return stk;
}

算法步骤：

1. 将所有点按 $x$ 坐标升序排序，$x$ 相同则按 $y$ 升序
2. 从左到右扫描，维护下凸壳：用叉积判断新点是否破坏凸性，破坏则弹出栈顶
3. 从右到左扫描，维护上凸壳，同样用叉积判断
4. 上下凸壳合起来即为完整凸包

核心在于利用叉积的符号判断当前栈顶的三个点是否构成 右转。若是右转则说明栈顶点在凸壳内，应弹出。

!
!
!
!

Graham 扫描法

选最左下点，按极角排序后单调栈维护。

double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
bool cmp(Point a, Point b) {
  double t = cross(a - p[1], b - p[1]);
  return t > 0 || (t == 0 && dis(a, p[1]) < dis(b, p[1]));
}
// 选 p[1] 为最左下点，排序后单调栈维护，叉积 <0 则弹栈

Graham 扫描法 vs Andrew

对比项	Graham 扫描	Andrew 算法
排序方式	极角排序	按 $x,y$ 排序
精度问题	极角排序涉及 atan2，浮点误差大	比较运算无浮点误差
代码复杂度	需要找最左下点，写比较函数	直接排序，分别扫上下
稳定性	共线点处理较麻烦	上下壳分离，天然稳定

结论：实践中 Andrew 算法更推荐，代码简洁且数值稳定性好。

旋转卡壳

对踵点对求直径（最远点对）：

double rotateCalipers(vector<Point> &h) {
  int n = h.size();
  double ans = 0;
  for (int i = 0, j = 1; i < n; ++i) {
    while ((h[(i + 1) % n] - h[i]).cross(h[(j + 1) % n] - h[j]) > 0)
      j = (j + 1) % n;
    ans = max(ans, dis2(h[i], h[j]));
    ans = max(ans, dis2(h[(i + 1) % n], h[(j + 1) % n]));
  }
  return sqrt(ans);
}

旋转卡壳 (Rotating Calipers) 是一种在凸包上对多组对踵点对依次处理的技术，常用于求解：

• 凸多边形直径（最远点对）：如上代码
• 凸多边形宽度（最近平行支撑线间距）
• 最小面积 / 最小周长外接矩形
• 两个凸包的最远 / 最近距离

核心思想：枚举凸包上的一条边，旋转”卡尺”找到距离该边最远的对踵点。由于凸包是凸的，对踵点单调移动，故总复杂度 $O(n)$。

!
!

题目	说明
P2742 圈奶牛	凸包模板
P1452 旋转卡壳	凸包直径
路径D-DSA算法刷题	更多练习

相关笔记：二维几何基础, 半平面交

相关链接

路径D-DSA算法刷题 | 二维几何基础 | 凸包 | 半平面交

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |