第 10.1 章：计算几何基础

10.1.0 从一道题出发：围栏问题

先看一道典型的 USACO 风格题目：

🌾 题目：围栏（Fence） 农夫 John 的牧场里有 N 根柱子（N ≤ 10⁵），第 i 根立在整数坐标 (xᵢ, yᵢ) 上（|xᵢ|, |yᵢ| ≤ 10⁶）。 John 想用一圈围栏把所有柱子围在内部或边界上。围栏是一圈首尾相连的线段，必须架在柱子上（每段围栏连接两根柱子）。 问：围栏最短是多少？（结果保留两位小数）

输入样例：

7
0 0
4 0
4 4
0 4
1 1
2 4
3 2

先试试你会的方法

思路 1：把柱子按某种顺序连起来？ 比如按 x 排序，相邻两根连一条边，再把首尾相连。对样例算一下：

排序后：(0,0) (0,4) (1,1) (2,4) (3,2) (4,0) (4,4)。相邻距离依次为 4、√2、√10、√5、√20、√10，再加首尾 (4,4)→(0,0) 的 4√2 ≈ 5.66。总共约 4+1.41+3.16+2.24+4.47+3.16+5.66 ≈ 24.1。

思路 2：直接目测样例。 仔细看这 7 个点：中间的 (1,1)、(2,4)、(3,2) 都被 (0,0)、(4,0)、(4,4)、(0,4) 组成的正方形「包住」了。正方形周长只有 16——比 24.1 短得多！

直觉告诉我们：最优围栏就是包住所有点的最小凸多边形——想象把一根橡皮筋套在所有柱子外面，松手后它绷紧成的形状，就是答案。

这个「橡皮筋形状」在计算几何中叫做凸包（Convex Hull）。求出凸包，围栏长度就是凸包的周长。

拆解这道题需要回答的问题

1. 怎么在代码里表示点、线段这些几何对象？→ 向量
2. 怎么判断「拐左还是拐右」？→ 叉积
3. 怎么高效求出凸包？→ Andrew 算法（排序 + 单调栈，O(N log N)）
4. 凸包还有什么用？→ 旋转卡壳（最远点对）、多边形面积、点在多边形内

第 10.1 章按这条线逐一展开：

学习目标：

• 定义点/向量结构体，用叉积判断方向（左转 / 右转 / 共线）
• 实现线段相交判定与多边形面积（鞋带公式）
• 用 Andrew 算法 O(N log N) 求凸包
• 用旋转卡壳 O(N) 求凸包直径（最远点对）

10.1.1 向量：计算几何的积木

点与向量

在平面直角坐标系里，点用坐标 (x, y) 表示。向量同样用两个数表示——从原点指向 (x, y) 的箭头。代码中二者共用一个结构体，但概念上要分清：点是位置，向量是位移。

计算几何的黄金法则：能用向量就不解方程。中学的 y = kx + b 斜截式有无数坑（垂直线斜率不存在、浮点误差），而向量运算大多是纯整数，又快又准。

typedef long long ll;

struct Pt {
    ll x, y;
};

Pt operator+(Pt a, Pt b) { return {a.x + b.x, a.y + b.y}; }
Pt operator-(Pt a, Pt b) { return {a.x - b.x, a.y - b.y}; }
bool operator==(Pt a, Pt b) { return a.x == b.x && a.y == b.y; }

减法 b - a 得到的是从 a 指向 b 的向量——这是第 10.1 章用得最多的操作。

⚠️ 整数 vs 浮点： 只要题目给的是整数坐标，就用 long long 存坐标、用整数叉积做判定，完全避免精度问题。只有最终求长度/面积时才转 double。

点积

两个向量 a、b 的点积（数量积）：

$$\mathbf{a} \cdot \mathbf{b} = a_x b_x + a_y b_y = |\mathbf{a}||\mathbf{b}|\cos\theta$$

几何意义： b 在 a 方向上的投影长度（乘上 |a|）。投影是正还是负，说明夹角是锐角还是钝角：

ll dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y; }

叉积：第 10.1 章的主角

两个向量 a、b 的叉积（向量积的 z 分量）：

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

几何意义： 以 a、b 为两条边的平行四边形的有向面积（三角形面积的 2 倍）。更重要的，它的符号告诉我们 b 在 a 的哪一侧：

方向判断表（站在 a 处朝 a 的方向看 b）：

ll cross(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }

验证一下：cross({1,0}, {0,1}) = 1×1 − 0×0 = 1 > 0，x 正方向的向量看 y 正方向确实在左边。✅

最常用的形式： 判断「沿 A→B→C 走，在 B 处怎么拐」——计算 cross(B−A, C−B)：

• > 0：左转（逆时针拐）
• = 0：直行（三点共线）
• < 0：右转（顺时针拐）

凸包算法的核心判据就是它。

⚠️ 为什么用 long long？ 坐标上限 10⁶ 时，叉积每项最大 10⁶ × 10⁶ = 10¹²，int 直接溢出。两个 10¹² 相减最大约 2×10¹²，long long（约 9.2×10¹⁸）足够安全。

10.1.2 常用判定：相交与距离

线段相交判定

判断线段 AB 与线段 CD 是否相交（包括端点碰到的情况）：

1. 跨立实验：若两线段相交，C、D 必在直线 AB 的两侧（或线上），A、B 也必在直线 CD 的两侧。用叉积判断：
   • d1 = cross(B−A, C−A)，d2 = cross(B−A, D−A)
   • 若 d1、d2 异号，说明 C、D 分居直线 AB 两侧
2. 特判共线：d1 = 0 时 C 在直线 AB 上，还需判断 C 是否在线段 AB 的范围内（用坐标范围即可）。

完整可编译代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Pt { ll x, y; };
Pt operator-(Pt a, Pt b) { return {a.x - b.x, a.y - b.y}; }

ll cross(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }

// 点 p 是否在线段 ab 上（先共线，再卡范围）
bool onSeg(Pt a, Pt b, Pt p) {
    return cross(b - a, p - a) == 0
        && min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x)
        && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

// 线段 ab 与线段 cd 是否相交（含端点接触、部分重叠）
bool segIntersect(Pt a, Pt b, Pt c, Pt d) {
    ll d1 = cross(b - a, c - a);   // c 相对直线 ab 的位置
    ll d2 = cross(b - a, d - a);   // d 相对直线 ab 的位置
    ll d3 = cross(d - c, a - c);   // a 相对直线 cd 的位置
    ll d4 = cross(d - c, b - c);   // b 相对直线 cd 的位置
    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))
        return true;               // 规范相交：互相跨立
    if (d1 == 0 && onSeg(a, b, c)) return true;  // 共线且范围重叠
    if (d2 == 0 && onSeg(a, b, d)) return true;
    if (d3 == 0 && onSeg(c, d, a)) return true;
    if (d4 == 0 && onSeg(c, d, b)) return true;
    return false;
}

int main() {
    // 三组测试
    printf("%d\n", segIntersect({0,0},{4,4},{0,4},{4,0})); // 1 对角线相交
    printf("%d\n", segIntersect({0,0},{1,1},{3,3},{4,4})); // 0 共线但不重叠
    printf("%d\n", segIntersect({0,0},{4,0},{4,0},{4,4})); // 1 端点接触
    return 0;
}

输出（已验证）：

1
0
1

点到线段的距离

第一步：点到直线的投影。 设点 P、直线过 A 且方向向量为 v（= B − A），则 P 在直线上的投影参数为：

$$t = \frac{\overrightarrow{AP} \cdot \mathbf{v}}{|\mathbf{v}|^2}$$

• t < 0：投影落在 A 之前 → 最近点是 A
• t > 1：投影落在 B 之后 → 最近点是 B
• 0 ≤ t ≤ 1：最近点是投影本身

typedef double db;
db dist(Pt a, Pt b) {
    db dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

// 点 p 到线段 ab 的距离
db distToSeg(Pt p, Pt a, Pt b) {
    Pt v = b - a;
    if (dot(v, p - a) < 0) return dist(p, a);          // 在 A 一侧
    if (dot(v, p - b) > 0) return dist(p, b);          // 在 B 一侧
    // 投影在线段上：距离 = |叉积| / |v|（平行四边形面积 ÷ 底）
    return abs(cross(v, p - a)) / sqrt((db)dot(v, v));
}

💡 投影落在线段中间时，为什么用叉积？ |cross(v, p−a)| 是平行四边形面积，除以底边长 |v| 恰好是高——也就是点到直线的距离。这比先算投影点再算距离少一次开方，也更不容易写错。

10.1.3 多边形：面积与点包含

鞋带公式：任意多边形面积

顶点按逆时针顺序为 $p_1, p_2, \dots, p_n$，则面积：

$$S = \frac{1}{2}\left|\sum_{i=1}^{n} p_i \times p_{(i \bmod n)+1}\right|$$

这就是鞋带公式（Shoelace Formula）——每项是相邻两个顶点坐标「交叉相乘再相减」，像系鞋带一样交错。

// 返回有向面积的 2 倍：顶点逆时针为正，顺时针为负
ll area2(vector<Pt>& poly) {
    ll s = 0;
    for (size_t i = 0; i < poly.size(); i++) {
        Pt &a = poly[i], &b = poly[(i + 1) % poly.size()];
        s += cross(a, b);
    }
    return s;
}
// 实际面积 = fabs(area2(poly)) / 2.0

为什么对？ 每一项 cross(pᵢ, pᵢ₊₁) 是三角形 O-pᵢ-pᵢ₊₁ 的有向面积（O 为原点）。把所有三角形加起来，多边形内部的面积被保留，外部的正负抵消，剩下的恰好是多边形的有向面积。

有向面积的妙用： 符号告诉你顶点顺序——正为逆时针，负为顺时针。这在读入顶点顺序不明时非常有用。

验证： 正方形 (0,0) (4,0) (4,4) (0,4)，area2 = (0−0)+(16−0)+(16−0)+(0−0) = 32，面积 = 32/2 = 16。✅

点在多边形内：射线法

从点 P 向右水平引一条射线，数它与多边形边的交点个数：

奇数个交点 → 在内部；偶数个 → 在外部。（「奇内偶外」）

直觉：射线每穿过一次边界，就「进出切换」一次。起点在内，穿奇数次后必在外。

// 点 p 是否在多边形内（在边界上也算在内）
bool inPolygon(Pt p, vector<Pt>& poly) {
    bool in = false;
    int n = poly.size();
    for (int i = 0, j = n - 1; i < n; j = i++) {
        Pt a = poly[i], b = poly[j];
        if (onSeg(a, b, p)) return true;          // 在边界上
        // 边 (a,b) 是否穿过 p 的水平射线？
        if ((a.y > p.y) != (b.y > p.y)) {
            // 求边与 y = p.y 的交点横坐标，判断是否在 p 右侧。
            // 整数坐标下用交叉相乘避免除法：
            // 交点 x = a.x + (p.y - a.y) * (b.x - a.x) / (b.y - a.y)
            // 判 x > p.x 等价于判 (b.x - a.x) * (p.y - a.y) > (p.x - a.x) * (b.y - a.y)
            if ((ll)(b.x - a.x) * (p.y - a.y) >
                (ll)(p.x - a.x) * (b.y - a.y))
                in = !in;
        }
    }
    return in;
}

验证： 正方形 (0,0) (4,0) (4,4) (0,4)：

• 点 (1,1)：内部 ✅
• 点 (5,5)：外部 ✅
• 点 (2,4)：边界上 ✅

边界情况的巧妙处理：(a.y > p.y) != (b.y > p.y) 这个条件天然处理了「射线恰好穿过顶点」的歧义——每条边只有「上端点严格高于 p.y、下端点不高于 p.y」时才算一次穿越，顶点被穿过的情形两条边只算一次。

10.1.4 凸包：Andrew 算法

定义

凸包是平面上能包住所有给定点的最小凸多边形。直观理解：一根橡皮筋套在所有点外面，绷紧后的形状。

为什么最优围栏是凸包？ 假设最优围栏在某处「凹」进去，由三角不等式，把凹进的两段替换成连接两个端点的一直线段，长度严格变小，且所有点仍在围栏内。所以最优解必须是凸的，且是包住所有点的最小凸多边形——即凸包。

算法思路：保持左转

想象沿凸包边界逆时针走一圈：每到一个顶点，都是左转（或直行）——凸多边形的所有内角 ≤ 180°。反过来，一旦途中有一步「右转」，这段路一定在凸包内部，不在边界上。

Andrew 算法把这条观察变成单调栈：

1. 排序：所有点按 x 为第一关键字、y 为第二关键字升序排序。排序后最左的点 p₀ 和最右的点 pₙ₋₁ 一定在凸包上（它们分别是 x 最小/最大的「极端点」）。
2. 下凸壳：从左到右扫描，维护一个栈。加入新点 P 时，若栈顶两个点 S₂、S₁（S₁ 为栈顶）到 P 形成右转——cross(S₁−S₂, P−S₂) < 0——就弹出 S₁，继续检查，直到左转或栈中只剩一个点，再把 P 入栈。得到凸包下半部分。
3. 上凸壳：从右到左再做一遍同样的扫描，得到上半部分。
4. 两壳拼接（去掉重复的端点）即得逆时针排列的凸包。

为什么弹栈？ 栈里的点是我们「目前相信在凸包上」的点。新点 P 使栈顶变成右转，意味着栈顶那个点被包在了三角形（S₂, S₁, P）内部——它不在边界上，必须淘汰。弹出的点不可能再「复活」：它已经在当前点集的凸包内部了。

        P（新点）
       /|
      / |   S₁ 在 S₂→P 连线的"凹侧"
  S₂ ●--+  ← S₁ 必须弹出
   \  |
    \ ● S₁
     \|    
      （下凸壳应为 S₂ → P 的直线）

复杂度： 排序 O(N log N)；扫描看似双重循环，但每个点至多入栈、出栈各一次，均摊 O(N)。总计 O(N log N)。

完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Pt { ll x, y; };
Pt operator-(Pt a, Pt b) { return {a.x - b.x, a.y - b.y}; }
bool operator<(Pt a, Pt b) { return a.x != b.x ? a.x < b.x : a.y < b.y; }
bool operator==(Pt a, Pt b) { return a.x == b.x && a.y == b.y; }

ll cross(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }

// 求凸包，返回逆时针排列的顶点（不保留边上的共线中间点）
vector<Pt> convexHull(vector<Pt> p) {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());  // 去重
    int n = p.size();
    if (n < 2) return p;
    vector<Pt> h(2 * n);
    int k = 0;
    // 下凸壳：从左到右
    for (int i = 0; i < n; i++) {
        // 叉积 <= 0：右转或共线 → 弹出（共线点不保留）
        while (k >= 2 && cross(h[k-1] - h[k-2], p[i] - h[k-2]) <= 0) k--;
        h[k++] = p[i];
    }
    // 上凸壳：从右到左（t 保证下壳不被破坏）
    for (int i = n - 2, t = k + 1; i >= 0; i--) {
        while (k >= t && cross(h[k-1] - h[k-2], p[i] - h[k-2]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);   // 最后一个点与第一个点相同，去掉
    return h;
}

double dist(Pt a, Pt b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

int main() {
    // 正方形 4 顶点 + 内部点 + 边上共线点
    vector<Pt> pts = {{0,0},{4,0},{4,4},{0,4},{1,1},{2,4},{3,2}};
    auto h = convexHull(pts);
    printf("凸包顶点数 = %zu\n", h.size());      // 4
    double per = 0;
    for (size_t i = 0; i < h.size(); i++)
        per += dist(h[i], h[(i + 1) % h.size()]);
    printf("周长 = %.2f\n", per);                 // 16.00
    return 0;
}

输出（已验证）：

凸包顶点数 = 4
周长 = 16.00

注意 (2,4) 在正方形上边 (0,4)–(4,4) 上，因为弹栈条件用了 <= 0（共线也弹出），它没有出现在结果中。如果题目需要保留边上的所有点（比如求边上整点数），把 <= 0 改成 < 0。

10.1.5 旋转卡壳：凸包直径

问题与思路

凸包直径 = 点集中最远两点的距离（最远点对一定都在凸包上，且是一对对踵点——能被两条平行线分别卡住的两个点）。

暴力枚举所有点对是 O(N²)。旋转卡壳利用凸包的有序性做到 O(N)：

逆时针枚举凸包的每条边，维护「离这条边最远的点」。边逆时针旋转时，对应的最远点也只会单调地逆时针前进，绝不回头——所以用一个双指针 j 同向推进即可。每个点最多被扫一圈，总移动 O(N)。

「离边最远」怎么比较？点到边的距离 = 叉积面积 ÷ 底边长，底相同，直接比叉积绝对值即可——全程整数，无精度问题。

        h[j+1]
       /      \
      /   ● h[j]  ← 离边 (h[i], h[i+1]) 最远的点
     /           \
    ●─────────────●
   h[i]          h[i+1]
   （边逆时针转，h[j] 也逆时针走）

核心代码

// 凸包直径的平方（整数坐标下全程无精度问题）
// h 为逆时针凸包，h.size() >= 2
ll diameter2(const vector<Pt>& h) {
    int n = h.size();
    if (n == 2) return dot(h[1]-h[0], h[1]-h[0]);
    ll ans = 0;
    for (int i = 0, j = 2; i < n; i++) {
        // 边 (h[i], h[i+1])：若 h[j+1] 离边更远，j 前进
        while (abs(cross(h[(i+1)%n] - h[i], h[(j+1)%n] - h[i]))
             > abs(cross(h[(i+1)%n] - h[i], h[j] - h[i])))
            j = (j + 1) % n;
        // 最远点对中必有 h[i] 或 h[i+1] 与 h[j] 配对
        ans = max(ans, max(dot(h[i] - h[j], h[i] - h[j]),
                           dot(h[(i+1)%n] - h[j], h[(i+1)%n] - h[j])));
    }
    return ans;
}

验证： 边长为 4 的正方形凸包，对角线 4√2，diameter2 = 32。✅

💡 为什么答案要同时检查 h[i] 和 h[i+1]？ j 是「离当前边最远」的点，但最远点对未必以边端点配对一定成立——稳妥起见两个端点都和 h[j] 比一次，仍不影响 O(N)。

⚠️ j 会绕圈吗？ 会，所以用 j = (j+1) % n 循环取模。这正是双指针「总移动量 O(N)」的体现：外层 i 走一圈，内层 j 合计也只走一圈。

10.1.6 实战：围栏问题完整程序

回到开篇的题目。算法：读入 N 个点 → Andrew 凸包 → 输出周长（两位小数）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Pt { ll x, y; };
Pt operator-(Pt a, Pt b) { return {a.x - b.x, a.y - b.y}; }
bool operator<(Pt a, Pt b) { return a.x != b.x ? a.x < b.x : a.y < b.y; }
bool operator==(Pt a, Pt b) { return a.x == b.x && a.y == b.y; }
ll cross(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }

vector<Pt> convexHull(vector<Pt> p) {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();
    if (n < 2) return p;
    vector<Pt> h(2 * n);
    int k = 0;
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(h[k-1] - h[k-2], p[i] - h[k-2]) <= 0) k--;
        h[k++] = p[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {
        while (k >= t && cross(h[k-1] - h[k-2], p[i] - h[k-2]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);
    return h;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<Pt> p(n);
    for (auto &q : p) scanf("%lld %lld", &q.x, &q.y);

    vector<Pt> h = convexHull(p);

    double ans = 0;
    for (size_t i = 0; i < h.size(); i++) {
        Pt a = h[i], b = h[(i + 1) % h.size()];
        double dx = a.x - b.x, dy = a.y - b.y;
        ans += sqrt(dx * dx + dy * dy);
    }
    printf("%.2f\n", ans);
    return 0;
}

样例输入：

7
0 0
4 0
4 4
0 4
1 1
2 4
3 2

样例输出：

16.00

（已编译运行验证：凸包为正方形 (0,0)(4,0)(4,4)(0,4)，周长 4×4 = 16.00。）

边界情况自查：

• N = 1：围栏长度 0（凸包退化为 1 点，周长循环算出 0）✅
• N = 2：两根柱子，围栏是「来回」两段，长度 2d ✅
• 所有点共线：<= 0 的弹栈条件会把中间点全部弹掉，凸壳退化为线段的两端点，周长 = 2d ✅

💡 USACO 真题对照： 这道题就是 USACO 5.1「Fencing the Cows」（圈奶牛）的翻版，也是 USACO Training Gateway 的经典入门题。Gold 实战中更常见的是凸包作为子步骤出现（如求凸包直径、面积后再做后续计算）。

⚠️ 常见错误

第 10.1 章总结

核心心法：

1. 整数到底——判定全部用整型叉积/点积，最后一步才开方
2. 叉积即方向——一切「左/右/共线」问题归约为叉积符号
3. 凸包是「外壳」——周长、直径、最远点对、最小覆盖，先想到凸包

练习题

🟢 简单

10.1-E1. 三角形面积 （Luogu P5684 风格） 给定三角形三个顶点的整数坐标（|x|, |y| ≤ 10⁹），输出面积的 2 倍（保证是整数）。 数据规模： 仅 3 个点。

10.1-E2. 点在哪里？ 给定一个 N 边形（顶点按逆时针给出）和 Q 个查询点，对每个点输出 INSIDE / OUTSIDE / BOUNDARY。 数据规模： 3 ≤ N ≤ 10⁵，1 ≤ Q ≤ 10⁵，坐标为绝对值 ≤ 10⁹ 的整数。

🟡 中等

J-M1. 圈奶牛 （USACO 5.1 Fencing the Cows / Luogu P2742） 给定 N 个点的坐标，求凸包周长，保留两位小数。 数据规模： 1 ≤ N ≤ 10⁴，坐标为绝对值 ≤ 10⁶ 的实数。

J-M2. 最远点对 （Luogu P1452 Beauty Contest） 给定平面上 N 个点，求任意两点的最大距离。 数据规模： 2 ≤ N ≤ 5×10⁴，|x|, |y| ≤ 10⁴。

🔴 困难

J-H1. 最小围栏周长 （POJ 1113 Wall 风格，USACO 铜牌变体改编） 国王要建围墙围住 N 个城堡，要求围墙离任意城堡的距离至少 L。求围墙最小长度。 数据规模： 1 ≤ N ≤ 1000，1 ≤ L ≤ 1000，坐标为绝对值 ≤ 10⁴ 的整数。