2026 年省选专题系列六：计算几何基础与凸包。

基础概念

  • 向量：有方向的线段
  • 点积：a·b = |a||b|cosθ
  • 叉积：a×b = |a||b|sinθ
  • 叉积判断：正为左，负为右，零共线

凸包算法

Andrew 算法

  1. 按 x 坐标排序
  2. 求上下凸壳
  3. 拼接成完整凸包
  4. 复杂度 O(n log n)

Graham 扫描

  1. 找一个基准点
  2. 按极角排序
  3. 用栈维护凸包

旋转卡壳

求凸包直径、最小矩形覆盖等。

经典应用

  • 凸包面积
  • 点在多边形内
  • 线段相交
  • 最近点对

省选一对一辅导：151 6522 2880