2026 年省选专题系列三：计算几何基础与凸包。
基础概念
- 向量：有方向的线段
- 点积：a·b = |a||b|cosθ
- 叉积：a×b = |a||b|sinθ
- 叉积判断：正为左，负为右，零共线
凸包算法
Andrew 算法：
- 按 x 坐标排序
- 求上下凸壳
- 拼接成完整凸包
- 复杂度 O(n log n)
Graham 扫描：
- 找一个基准点
- 按极角排序
- 用栈维护凸包
旋转卡壳
求凸包直径、最小矩形覆盖等。
经典应用
- 凸包面积
- 点在多边形内
- 线段相交
- 最近点对
省选一对一辅导：151 6522 2880