计算几何基础

前言

计算几何在竞赛中不算高频，但一旦出现就是”会就会、不会就不会”的题。核心工具只有一个：向量叉积。叉积能判断方向（左/右/共线）、计算面积、检测线段相交。掌握了叉积，几何题就解决了一半。

问题的本质

叉积是万能钥匙

两个二维向量 $\vec{a} = (a_x, a_y)$ 和 $\vec{b} = (b_x, b_y)$ 的叉积：

$\vec{a} \times \vec{b} = a_x b_y - a_y b_x$

叉积的几何意义：

• 正数：$\vec{b}$ 在 $\vec{a}$ 的逆时针方向（左侧）
• 负数：$\vec{b}$ 在 $\vec{a}$ 的顺时针方向（右侧）
• 零：共线

为什么叉积这么重要？因为几乎所有几何判断都可以归结为”方向”：

• 三点共线？$\vec{AB} \times \vec{AC} = 0$
• 点 $P$ 在有向直线 $AB$ 的哪一侧？$\vec{AB} \times \vec{AP}$ 的符号
• 两个线段是否相交？两次叉积判方向 + 一次叉积判共线位置
• 多边形面积？鞋带公式 $= \frac{1}{2}|\sum \vec{P_i P_{i+1}} \times \vec{P_i O}|$

精度问题

几何题最容易 WA 的原因不是算法，而是浮点精度。两个原则：

1. 能用整数就用整数（叉积在整数坐标下是精确的）。
2. 比较用 eps（通常 $10^{-9}$），不要直接 ==。

理论 + 代码

基本模板

#include <cmath>
const double EPS = 1e-9;
const double PI = acos(-1.0);

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator+(Point p) { return {x+p.x, y+p.y}; }
    Point operator-(Point p) { return {x-p.x, y-p.y}; }
    Point operator*(double t) { return {x*t, y*t}; }
    double norm() { return x*x + y*y; }
    double abs() { return sqrt(norm()); }
};

double cross(Point a, Point b) { return a.x*b.y - a.y*b.x; } // ① 叉积
double dot(Point a, Point b) { return a.x*b.x + a.y*b.y; }   // ② 内积

// 点 p 相对于有向线段 ab 的方向
int ccw(Point a, Point b, Point p) {
    Point ab = b - a, ap = p - a;
    double c = cross(ab, ap);                              // ③ 叉积判方向
    if (c > EPS) return 1;                                 // ④ 逆时针（左侧）
    if (c < -EPS) return -1;                               // ⑤ 顺时针（右侧）
    return 0;                                              // ⑥ 共线
}

逐行解析：

• ① $\vec{a} \times \vec{b} = a_x b_y - a_y b_x$。
• ② 内积 $\vec{a} \cdot \vec{b} = a_x b_x + a_y b_y$，用于投影和角度计算。
• ③⑥ ccw 函数返回方向：+1=左，-1=右，0=共线。

凸包（Andrew 单调链）

#include <vector>
#include <algorithm>
using namespace std;

vector<Point> convex_hull(vector<Point>& pts) {
    sort(pts.begin(), pts.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });                                                    // ① 按 x 排序
    int n = pts.size();
    vector<Point> ch(2 * n);
    int k = 0;
    // ② 下凸壳
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(ch[k-1]-ch[k-2], pts[i]-ch[k-1]) <= 0) k--;
        ch[k++] = pts[i];
    }
    // ③ 上凸壳
    for (int i = n-2, t = k+1; i >= 0; i--) {
        while (k >= t && cross(ch[k-1]-ch[k-2], pts[i]-ch[k-1]) <= 0) k--;
        ch[k++] = pts[i];
    }
    ch.resize(k - 1);                                     // ④ 去掉重复起点
    return ch;
}

逐行解析：

• ① 按 $x$ 坐标排序（$x$ 相同按 $y$）。
• ② 从左到右扫描，维护下凸壳。叉积 $\le 0$ 说明右拐或共线，弹出。
• ③ 从右到左扫描，维护上凸壳。
• ④ 起点被加入了两次，去掉一个。

多边形面积（鞋带公式）

double polygon_area(vector<Point>& poly) {
    double area = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++)
        area += cross(poly[i], poly[(i+1)%n]);            // ① 叉积累加
    return abs(area) / 2.0;                               // ② 取绝对值除以 2
}

逐行解析：

• ① $2S = |\sum_{i} (x_i y_{i+1} - x_{i+1} y_i)| = |\sum \text{cross}(P_i, P_{i+1})|$。
• ② 叉积之和可能为负（顶点顺时针排列），取绝对值。

点在多边形内判定（射线法）

bool point_in_polygon(Point p, vector<Point>& poly) {
    int n = poly.size();
    bool inside = false;
    for (int i = 0, j = n-1; i < n; j = i++) {
        if ((poly[i].y > p.y) != (poly[j].y > p.y) &&    // ① 跨越水平线
            p.x < (poly[j].x - poly[i].x) * (p.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x) // ② 交点在右侧
            inside = !inside;                             // ③ 翻转状态
    }
    return inside;
}

逐行解析：

• ① 从点 $P$ 向右发射水平射线，检查与每条边是否相交。
• ② 边的 $x$ 坐标大于 $P$ 的 $x$ 坐标，说明交点在右侧。
• ③ 每穿过一条边，内外状态翻转。

例题

例题 1：M&A 033 — Distance（点到线段距离）

题目：三点 $A, B, C$，求点 $A$ 到线段 $BC$ 上点的最短距离。

—— AtCoder M&A 033

分析：垂足是否在线段上？用内积判断。如果在，答案为点到直线距离（叉积除以线段长度）；否则为到两个端点距离的较小值。

代码：

#include <cstdio>
#include <cmath>
using namespace std;

double cross(double ax, double ay, double bx, double by) { return ax*by - ay*bx; }
double dot(double ax, double ay, double bx, double by) { return ax*bx + ay*by; }

int main() {
    double ax, ay, bx, by, cx, cy;
    scanf("%lf%lf%lf%lf%lf%lf", &ax, &ay, &bx, &by, &cx, &cy);

    double ba_x = ax-bx, ba_y = ay-by;                 // ① BA 向量
    double bc_x = cx-bx, bc_y = cy-by;                 // ② BC 向量
    double ca_x = ax-cx, ca_y = ay-cy;                 // ③ CA 向量

    if (dot(ba_x, ba_y, bc_x, bc_y) < 0) {             // ④ A 在 B 的外侧
        printf("%.10f\n", sqrt(ba_x*ba_x + ba_y*ba_y));
    } else if (dot(ca_x, ca_y, -bc_x, -bc_y) < 0) {   // ⑤ A 在 C 的外侧
        printf("%.10f\n", sqrt(ca_x*ca_x + ca_y*ca_y));
    } else {                                            // ⑥ 垂足在线段上
        double d = abs(cross(ba_x, ba_y, bc_x, bc_y)) / sqrt(bc_x*bc_x + bc_y*bc_y);
        printf("%.10f\n", d);
    }
}

逐行解析：

• ④⑤ 用内积判断 $A$ 相对于线段 $BC$ 的投影位置。$\vec{BA} \cdot \vec{BC} < 0$ 表示 $A$ 在 $B$ 的”后面”。
• ⑥ 垂足在线段上，距离 = $|\vec{BA} \times \vec{BC}| / |\vec{BC}|$。

---

例题 2：M&A 036 — Colon（时针分针端点距离）

题目：时针长 $A$ 厘米，分针长 $B$ 厘米。0 点时两针重合，$H$ 时 $M$ 分时两针自由端相距多远？

数据范围：$1 \le A, B \le 1000$，$0 \le H \le 11$，$0 \le M \le 59$

—— AtCoder M&A 036

分析：时针每 12 小时转 1 圈（$30°$/小时），分针每 1 小时转 1 圈（$6°$/分钟）。$H$ 时 $M$ 分时：时针角度 $= 30H + 0.5M$ 度，分针角度 $= 6M$ 度。两针夹角 $= |\theta_h - \theta_m|$。端点距离由余弦定理：$d = \sqrt{A^2 + B^2 - 2AB\cos\theta}$。

输入样例：3 4 9 0 输出：5.00000000000000000000

验证：9:00 时针在 270° (9×30)，分针在 0°。$\theta = 90°$。$d = \sqrt{9+16-0} = \sqrt{25} = 5$。✓

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    double A, B, H, M;
    scanf("%lf%lf%lf%lf", &A, &B, &H, &M);

    double theta_h = 30.0 * H + 0.5 * M;               // ① 时针角度（度）
    double theta_m = 6.0 * M;                           // ② 分针角度（度）
    double diff = abs(theta_h - theta_m);
    diff = min(diff, 360.0 - diff);                     // ③ 取锐角

    double rad = diff * M_PI / 180.0;                   // ④ 转弧度
    double ans = sqrt(A*A + B*B - 2*A*B*cos(rad));     // ⑤ 余弦定理
    printf("%.20f\n", ans);
}

逐行解析：

• ① 时针每分钟转 $0.5°$，每小时 $30°$。
• ② 分针每分钟转 $6°$。
• ③ 两针之间的角度取较小值。
• ⑤ 余弦定理：$d^2 = A^2 + B^2 - 2AB\cos\theta$。

---

例题 3：M&A 098 — Polygon and Point（点在多边形内）

题目：$N$ 个顶点的多边形和点 $(A, B)$，判断点是否在多边形内部。

—— AtCoder M&A 098

分析：射线法。从点向右发射水平射线，统计与多边形边的交点数。奇数→内部，偶数→外部。

代码：

#include <cstdio>
#include <vector>
using namespace std;

double X[109], Y[109];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%lf%lf", &X[i], &Y[i]);
    double A, B;
    scanf("%lf%lf", &A, &B);

    bool inside = false;
    for (int i = 0, j = N-1; i < N; j = i++) {
        if ((Y[i] > B) != (Y[j] > B)) {                // ① 跨越水平线 y=B
            double x_int = (X[j]-X[i]) * (B-Y[i]) / (Y[j]-Y[i]) + X[i];
            if (A < x_int) inside = !inside;            // ② 交点在右侧→翻转
        }
    }
    printf("%s\n", inside ? "INSIDE" : "OUTSIDE");
}

逐行解析：

• ①② 经典射线法：每次穿越多边形边界，内外状态翻转。

---

例题 4：凸包应用——M&A 034 Nearest Points（最近点对）

题目：$N$ 个点，求最近点对距离。$2 \le N \le 2000$。

—— AtCoder M&A 034

分析：分治法。按 $x$ 坐标排序后分成左右两半，递归求两半的最近点对，然后检查跨两半的点对。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cfloat>
using namespace std;

double closest_pair(vector<pair<double,double>>& pts, int lo, int hi) {
    if (hi - lo <= 3) {                                 // ① 暴力处理小规模
        double best = DBL_MAX;
        for (int i = lo; i < hi; i++)
            for (int j = i+1; j < hi; j++) {
                double dx = pts[i].first - pts[j].first;
                double dy = pts[i].second - pts[j].second;
                best = min(best, dx*dx + dy*dy);
            }
        return best;
    }
    int mid = (lo + hi) / 2;
    double midx = pts[mid].first;
    double d = min(closest_pair(pts, lo, mid),          // ② 左半
                   closest_pair(pts, mid, hi));          // ③ 右半

    // ④ 收集距中线 <= sqrt(d) 的点
    vector<pair<double,double>> strip;
    for (int i = lo; i < hi; i++)
        if ((pts[i].first - midx) * (pts[i].first - midx) < d)
            strip.push_back(pts[i]);

    sort(strip.begin(), strip.end(), [](auto& a, auto& b) {
        return a.second < b.second;                     // ⑤ 按 y 排序
    });
    for (int i = 0; i < (int)strip.size(); i++)
        for (int j = i+1; j < (int)strip.size() && (strip[j].second-strip[i].second)*(strip[j].second-strip[i].second) < d; j++) {
            double dx = strip[i].first - strip[j].first;
            double dy = strip[i].second - strip[j].second;
            d = min(d, dx*dx + dy*dy);
        }
    return d;
}

int main() {
    int N;
    scanf("%d", &N);
    vector<pair<double,double>> pts(N);
    for (int i = 0; i < N; i++) scanf("%lf%lf", &pts[i].first, &pts[i].second);
    sort(pts.begin(), pts.end());                       // ⑥ 按 x 排序
    printf("%.10f\n", sqrt(closest_pair(pts, 0, N)));
}

逐行解析：

• ① 小规模暴力：$O(1)$（最多 3 个点）。
• ②③ 分治递归。
• ④ 收集中线附近 $\sqrt{d}$ 范围内的点。
• ⑤⑥ 跨越检查时按 $y$ 排序，内层循环至多 7 次（经典结论）。

参考文献

基础练习 — アルゴリズムと数学 演習問題集

• 033 Distance（点到线段距离）【例题】
• 034 Nearest Points（最近点对）【例题】
• 035 Two Circles（两圆关系）
• 036 : (Colon)（时针分针距离）【例题】
• 037 Intersection（线段相交判定）
• 098 Polygon and Point（点在多边形内）【例题】
• 103 Circle Packing（圆的填充）

实战练习 — 競プロ典型 90 問

• 009 Three Point Angle（★6，三点角度）
• 036 Max Manhattan Distance（★5，旋转 45°）
• 041 Piles in AtCoder Farm（★7，凸包+旋转卡壳）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化