usaco-5.1.1 圈奶牛

形式化题目

给定平面上的点集 $S = \{P_1, P_2, \dots, P_N\}$ ， $P_i = (X_i, Y_i)$ ，坐标均为实数。

求一条闭合曲线 $C$ ，使得每个 $P_i$ 都落在 $C$ 上或 $C$ 的内部，并且 $C$ 的长度最小；即求 $\min_C |C|$ 这一最优值。

样例： $S = \{(4,8), (4,12), (5,9.3), (7,8)\}$ ，最短闭合曲线是三角形 $(4,8) \to (7,8) \to (4,12) \to (4,8)$ ，周长 $3 + 5 + 4 = 12$ 。

正解

思路

第一步：把"最短围栏"换成"凸包周长"

围栏是一条闭合曲线，看起来要搜的对象是无穷多条曲线。但有两条性质能把它压成一个确定的几何对象：

拐点一定取自输入点。 若最优围栏的拐点 $P$ 不是输入点，设它两侧的拐点是 $A, B$ ，把 $P$ 沿角平分线朝多边形内部挪一点得到 $P'$ 。由三角不等式， $|AP'| + |P'B| < |AP| + |PB|$ ，包含性不变而周长变短，矛盾。
最优围栏一定是凸的。 若它有凹口，用弦代替凹口内的折线，长度更短且包含的区域更大，同样矛盾。

一个凸多边形能围住 $S$ ，当且仅当它能围住 $S$ 的凸包；而在所有能围住凸包的凸多边形里，周长最小的就是凸包本身。于是答案恰好是点集凸包的周长，问题变成 “求出凸包顶点序列”。

以样例为证： $(5, 9.3)$ 落在其余三点构成的三角形内部，去掉它周长不变，而 $3 + 5 + 4 = 12$ 就是答案。下图标出这三个围栏顶点和那个可以省略的内部点。

样例：三个放牧点围成三角形，第四个点在内部，三条边长 3 + 5 + 4 = 12

图上红点是围栏顶点，空心蓝点是落在三角形内部的放牧点。读者应注意到：内部点既不影响包含关系、也不贡献周长，所以候选顶点只需考虑凸包上的点。

第二步：Andrew 单调链求凸包

候选顶点定了，还要知道它们按什么顺序连。 $N$ 最大 $10000$ ，允许 $O(N \log N)$ ，所以"排一次序 + 两遍线性扫描"是完全够用的复杂度，不必考虑更重的做法。做法的骨架是先排序，再左右各扫一遍：

把点按 $(x, y)$ 升序排序。这样最左点就是 $y$ 最小的那个，最右点就是 $y$ 最大的那个，两条链的端点被固定下来。
从左往右扫一遍，维护一个栈，得到下凸壳（从左下走到右上）。
从右往左再扫一遍，同样维护栈，得到上凸壳（从右上走回左下）。
两个栈各自的首尾端点是同一个最左点、最右点，去掉重复后拼接，就得到了逆时针排列的完整凸包。

关键在于扫描时该不该保留新点。维护的信息是"栈里已经构成一段凸壳"，新点 $p$ 进来后，要看栈顶 $B$ （及其前驱 $A$ ）相对 $p$ 的转向：

cross(A, B, p) > 0： $A \to B \to p$ 左转， $B$ 仍是凸壳顶点，保留；
cross(A, B, p) < 0：右转， $B$ 被"顶"进了新边的下方，不可能是顶点，弹出；
cross(A, B, p) = 0： $A, B, p$ 共线， $B$ 落在边 $A p$ 上。留着不改周长，但弹掉能让凸包严格凸、没有冗余顶点，所以也弹出。

三种情况合起来就是一句判断：只要新点不能让栈顶保持左转（cross(...) > 0 不成立），就把栈顶弹掉。代码把这个判断写成 if cross(...) > 0: break 加 pop()，比把条件挤进 while 里更好读。下面的特写图把这三条判定并排画出来，红色表示要弹掉的点。

左转时中间点 $B$ 是凸壳顶点；右转说明 $B$ 凹进去了；共线说明 $B$ 在边上多余。因此只要弹出条件写成"不能左转就弹"，一次扫描就能得到正确的凸壳。

第三步：累加闭合周长

凸包顶点序列首尾相接才是围栏，所以相邻顶点两两求欧氏距离，最后再把末顶点连回首顶点。实现上用 pairwise(ring + ring[:1])：把首顶点复制到末尾，一次推导式就能同时处理"内部相邻边"和"闭合边"。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 07:08
# update_at: 2026-10-01 07:08

import sys
from itertools import pairwise
from math import hypot

Scalar = int | float
Point = tuple[Scalar, Scalar]


def cross(o: Point, a: Point, b: Point) -> Scalar:
    """叉积 (a - o) × (b - o)：> 0 表示 o→a→b 左转，= 0 表示三点共线。"""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def convex_hull(points: list[Point]) -> list[Point]:
    """单调链求凸包：返回逆时针顶点序列，边上的共线点只保留线段两端。

    先按 (x, y) 升序排序，于是"最左点取最下、最右点取最上"；
    新点不能与栈顶构成左转时，栈顶就不可能是凸包顶点，弹掉。
    """
    ordered = sorted(points)
    lower: list[Point] = []                     # 左下 → 右上的下凸壳
    for p in ordered:
        while len(lower) >= 2:
            if cross(lower[-2], lower[-1], p) > 0:
                break                           # 左转：栈顶仍是凸壳顶点
            lower.pop()                         # 右转或共线：栈顶多余
        lower.append(p)
    upper: list[Point] = []                     # 右上 → 左下的上凸壳
    for p in reversed(ordered):
        while len(upper) >= 2:
            if cross(upper[-2], upper[-1], p) > 0:
                break
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]              # 首尾两点在两条链里各出现一次


def perimeter(points: list[Point]) -> float:
    """正解：围住一个点集的最短闭合曲线就是它的凸包，答案即凸包周长。

    退化为凸包只有 1 个点时周长自然是 0；只剩 2 个端点（点全共线）时，
    "走个来回"是最短的闭合曲线，周长同样由闭合折线公式自然算出。
    """
    ring = convex_hull(points)                  # 逆时针凸包顶点序列
    # ring[:1] 把首顶点复制到末尾，这样 pairwise 也会算出闭合边
    return sum(hypot(q[0] - p[0], q[1] - p[1]) for p, q in pairwise(ring + ring[:1]))


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    points: list[Point] = [(float(next(data)), float(next(data))) for _ in range(n)]
    print(f"{perimeter(points):.2f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:40
 * update_at: 2026-10-06 11:41
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 10005;

typedef long long ll;

struct Point {
    double x;
    double y;
};

Point pts[MAXN];        // 输入的所有放牧点
Point lower_hull[MAXN]; // 下凸壳，从左下走到右上
Point upper_hull[MAXN]; // 上凸壳，从右上走回左下
Point hull[MAXN];       // 拼接后的逆时针凸包顶点序列

int n;

// 按 (x, y) 升序比较，排序后最左点取最下、最右点取最上。
bool cmp_point(Point a, Point b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

// 叉积 (a - o) × (b - o)：> 0 表示 o -> a -> b 左转，= 0 表示三点共线。
double cross(Point o, Point a, Point b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

// 两点之间的欧氏距离。
double dist(Point a, Point b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

// 求点集凸包的周长，即围住所有放牧点的最短围栏长度。
double convex_hull_perimeter() {
    sort(pts + 1, pts + n + 1, cmp_point);

    // 下凸壳：从左往右扫，新点不能与栈顶构成左转就弹出栈顶。
    int lower_cnt = 0;
    for (int i = 1; i <= n; i++) {
        while (lower_cnt >= 2 &&
               cross(lower_hull[lower_cnt - 1], lower_hull[lower_cnt], pts[i]) <= 0) {
            lower_cnt--;
        }
        lower_hull[++lower_cnt] = pts[i];
    }

    // 上凸壳：从右往左扫，弹出条件与下凸壳完全一致。
    int upper_cnt = 0;
    for (int i = n; i >= 1; i--) {
        while (upper_cnt >= 2 &&
               cross(upper_hull[upper_cnt - 1], upper_hull[upper_cnt], pts[i]) <= 0) {
            upper_cnt--;
        }
        upper_hull[++upper_cnt] = pts[i];
    }

    // 两条链的首尾端点是同一对最左、最右点，各自去掉末顶点后拼接。
    int hull_cnt = 0;
    for (int i = 1; i <= lower_cnt - 1; i++) {
        hull[++hull_cnt] = lower_hull[i];
    }
    for (int i = 1; i <= upper_cnt - 1; i++) {
        hull[++hull_cnt] = upper_hull[i];
    }

    // 闭合折线周长：相邻顶点两两求距离，末顶点再连回首顶点。
    double ans = 0.0;
    for (int i = 1; i <= hull_cnt; i++) {
        int next_pos = i + 1;
        if (next_pos > hull_cnt) next_pos = 1;
        ans += dist(hull[i], hull[next_pos]);
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf %lf", &pts[i].x, &pts[i].y);
    }

    printf("%.2f\n", convex_hull_perimeter());
    return 0;
}

复杂度

时间复杂度：排序 $O(N \log N)$ ；下凸壳、上凸壳各扫描一遍，每个点最多入栈一次、出栈一次，合计 $O(N)$ ；求周长 $O(h) \subseteq O(N)$ 。总计 $O(N \log N)$ ，与标准 C++ 凸包解法同阶。
空间复杂度：排序后的点表、两个点栈、凸包序列均为 $O(N)$ 。

总结

最短围栏不是一条要搜索的曲线，而是点集的凸包边界：拐点取自输入点 + 最优解必凸，这两步把问题压成了确定的几何对象。
凸包顶点用 Andrew 单调链求：排序固定两端点，两条链各扫一遍；新点不能与栈顶构成左转（cross(A, B, p) <= 0）时弹掉栈顶。
求周长时把首顶点复制到末尾，用 pairwise 一次处理闭合边， $O(N \log N)$ 全部结束。
边界：凸包退化成 1 个点时周长是 0.00；退化成 2 个端点（点全共线）时，最短闭合曲线就是沿线段走个来回，即两倍线段长。两种情况都由闭合折线公式自然算出，代码里不需要额外的 if 分支。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6
7
8N 个放牧点
`- 关键观察 1：拐点取自输入点（三角不等式）
   `- 关键观察 2：最优围栏必凸（凹口换成弦更短）
      `- 模型：最短围栏 = 点集凸包的周长
         |- 排序：按 (x, y) 升序，固定最左/最右端点
         |- 下凸壳：从左往右扫，不能左转（cross <= 0）就弹栈顶
         |- 上凸壳：从右往左扫，同样的弹出条件
         `- 拼接去重 → 逆时针顶点序列 → 相邻距离求和 + 闭合边 = 答案

先看前两个节点如何把"搜索一条曲线"压成"求一个确定的几何对象"，再顺着三个分支看单调链怎样在两遍线性扫描里得到凸包，最后一步只是把顶点序列的边长加起来。图中只保留正文已经证明过的关系，不替代正文中的样例推演与复杂度分析。

目录

形式化题目

正解

思路

第一步：把"最短围栏"换成"凸包周长"

第二步：Andrew 单调链求凸包

第三步：累加闭合周长

代码

复杂度

总结

图示解析