第一次在题单里看到 “UVa 1084 Deer-Proof Fence” 的时候，我以为是个纯几何模拟题：给围栏、给坐标，算算有没有鹿能钻进去就完事。结果读完题发现完全不是那回事——这题表面是围栏，内核是把一堆点分成尽量少的组，每组能被一个半径固定的圆盖住。说白了，它是披着计算几何外衣的状态压缩集合覆盖问题。这篇文章就把我的完整推导过程、候选圆生成原理、DP 状态设计和浮点数坑全部写清楚，给同样被这题卡住的人一个能直接照着写的思路。
1. 题面到底在说什么：从“鹿吃树”到“半径差”的等价变换
题目故事大致是这样的：你有一片果园，里面种了 N 棵树，每棵树可以看成一个点。为了防止鹿进来吃，你要围若干个圆形围栏。每个围栏的半径是固定的 R。但鹿很狡猾，它的脖子可以伸进围栏一段距离 D，也就是说，围栏里面距离围栏线不超过 D 的树，鹿还是能吃到。
想清楚这一层，等价的几何模型就出来了：假设某个围栏的圆心在 O，围栏半径 R。一棵树如果到圆心距离是 ρ，那么它到围栏线的距离就是 R - ρ。只有当 R - ρ 比 D 大的时候，这棵树才是安全的。换句话说，一棵树安全当且仅当：
ρ < R - D
所以每一个围栏真正能保护到的范围，是以围栏圆心为中心、半径为 C = R - D 的一个圆。题目就变成了：要放最少多少个半径为 C 的圆，才能把所有 N 个点全部盖住。
这里有个很容易忽略的边界情况：如果 R ≤ D，C ≤ 0，那意味着即使树刚好长在围栏正中心，鹿伸脖子也能吃到，一个围栏连一棵树都保护不了。此时答案就是 N，每个点单独一个围栏。这个特判不做，后面几何代码里 C 会出现负数或者 0，h2 的 sqrt 直接当场爆炸。
还需要注意，题目原文里那两个参数用什么字母、哪个在前哪个在后，不同版本可能不同。你只要搞清楚“有效半径 = 围栏半径 - 鹿可伸长度”这个关系，读入顺序按题目描述微调就行。
清楚了模型之后，这题就从一个“围栏几何题”变成了一个纯粹的优化题：有 N 个点，你可以任意放置半径为 C 的圆，每个圆能覆盖住若干点，问最少需要几个圆。这可不是简单的贪心，后面会说为什么。
2. 状态压缩 DP 的大框架：N≤20 决定了做法
这个问题的本质是集合覆盖（Set Cover），在一般情况下是 NP 难问题。但 N 只有 20 左右，因为每个点是“被覆盖”或者“没被覆盖”两种状态，所以我们完全可以把“当前已经覆盖了哪些点”压成一个整数位掩码，做状态压缩 DP。
设全集是 (1 << N) - 1。dp[mask] 表示覆盖掉 mask 里这些点，最少需要多少个半径为 C 的圆。初始 dp[0] = 0，目标是 dp[全集]。
朴素想法是枚举 mask 的子集划分，比如 dp[mask] = min(dp[mask], dp[mask ^ sub] + 1)，其中 sub 是一个圆能覆盖的点集。但子集枚举是 3^N 的复杂度，N=20 的时候完全不可行。正确的做法是：每次只看 mask 里最低位的那个点 low。
为什么只看最低位就够了？因为不管 mask 有多大，最后一定是由某一个圆把 low 这个点盖住的。我们枚举所有能覆盖 low 点的候选圆 circleMask，然后让这个圆去覆盖 mask 里它能覆盖的那部分，剩余的部分继续递归。转移式可以写成：
dp[mask] = min(dp[mask & ~circleMask] + 1)
这里 circleMask 是某个圆实际覆盖的点集。注意 mask & ~circleMask 一定小于 mask，因为 circleMask 至少包含 low 点，所以这个余集一定比原 mask 少至少一个点，dp 值一定已经被算过了。按 mask 从小到大枚举，一次扫描就能把所有状态算完，不需要递归。
用“最低位出发”而不是“所有子集出发”，本质上是对搜索空间做了一次剪枝：每个状态只关心覆盖它最低位的那些圆，而不是所有圆的所有子集。这个优化非常关键，否则 3^20 的状态划分根本跑不动。
伪代码大概是：
dp[0] = 0 for mask = 1 .. (1<<N)-1: low = 最低位对应的点编号 for 每个候选圆 circleMask: if circleMask 覆盖 low: dp[mask] = min(dp[mask], dp[mask & ~circleMask] + 1)到这里，核心只剩下最后一个问题：候选圆到底怎么列？不可能枚举平面上所有圆心，但接下来会证明，我们只需要看数量为 O(N²) 的“特殊圆”。
3. 候选圆生成：为什么只需枚举“过两点的圆”
这是整道题我最喜欢的地方。直觉上，平面上能放圆心的位置是连续的，凭什么只列 O(N²) 个候选？因为有一个经典的几何结论。
假设某个最优解里有一个圆盖住了点集 S，|S| ≥ 2。如果这个圆的边界上没有任何点，说明所有 S 里的点都在圆内部，圆心一定可以朝某个方向平移一段距离，直到某个点碰上边界；碰上一个点之后，如果只有这一个点在边界上，还可以以这个点为支点略微旋转圆，直到第二个点也碰到边界。这个过程中圆始终在覆盖 S，不会漏点。所以，一定存在一个同样能覆盖住 S 的圆，它的边界经过 S 中至少两个点。
于是“最优解里的圆”只需要到下面两类里找：
- 圆心直接放在某个点上，用来覆盖单点。比如某个点周围 2C 范围里没有其他点，必须为它单独放一个圆；
- 圆心在以两个点为圆心、半径为 C 的两个圆的交点上，也就是过这两个点、半径为 C 的圆。注意两个点距离超过 2C 的时候没有交点，说明不可能用一个半径 C 的圆同时盖住这两个点。
有人会问：三个点刚好在一个半径为 C 的圆上，但其中任意两个点的交点圆没盖住第三个点怎么办？这种情况其实不会漏。因为那个同时过三点的圆，本身就同时过其中两个点，它一定在这两个点所生成的两个交点圆之一里。也就是说，我们枚举的“过两点的圆”已经包含了它。
具体算两个交点圆很直接。设两个点为 A、B，距离为 d，中点 M。圆的半径 C 已知。根据直角三角形，从 M 到圆心的距离 h 为：
h = sqrt(C² - (d/2)²)
圆心就在过 M、垂直于 AB 的方向上，距离 M 为 h 的位置，左右各一个。写成代码就是：
double dxb = p[j].x - p[i].x; double dyb = p[j].y - p[i].y; double d = sqrt(dxb * dxb + dyb * dyb); if (d > 2.0 * C + EPS) continue; double h2 = C * C - (d / 2.0) * (d / 2.0); if (h2 < 0) h2 = 0; double h = sqrt(h2); double mx = (p[i].x + p[j].x) / 2.0; double my = (p[i].y + p[j].y) / 2.0; double vx = -dyb / d; // 垂直单位向量 double vy = dxb / d; // 两个候选圆心 Point c1(mx + vx * h, my + vy * h); Point c2(mx - vx * h, my - vy * h);得到圆心之后，把这个圆能覆盖的所有点压成一个 mask，存进候选列表。具体是遍历所有点，只要距离平方 ≤ C² + eps 就置位。
这里我多说一句：单点圆不能省。看似过两点的圆已经覆盖了大部分情况，但如果一个点附近 2C 范围内没有其他点，它唯一可行方案就是单独放一个圆，而这个“单独圆”的候选圆心可以不经过任何其他点。把圆心放在这个点本身，是最稳妥、最少费脑筋的做法。
4. 完整 C++ 实现：从几何到 DP 一次跑通
下面是我整理出来的完整代码，按上文思路，先算有效半径 C，特判无解情况；然后枚举单点圆和两点圆；最后状压 DP。代码里有必要的话我都写了注释。
#include <bits/stdc++.h> using namespace std; const double EPS = 1e-9; struct Point { double x, y; Point(double x_ = 0.0, double y_ = 0.0) : x(x_), y(y_) {} }; double dist2(const Point& a, const Point& b) { double dx = a.x - b.x; double dy = a.y - b.y; return dx * dx + dy * dy; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; double R, D; int kase = 0; while (cin >> n && n) { cin >> R >> D; vector<Point> p(n); for (int i = 0; i < n; ++i) { cin >> p[i].x >> p[i].y; } cout << "Case " << ++kase << ": "; double C = R - D; if (C <= EPS) { cout << n << '\n'; continue; } vector<int> circles; // 给定圆心，把覆盖到的点压成掩码 auto addCircle = [&](const Point& c) { int mask = 0; for (int j = 0; j < n; ++j) { if (dist2(c, p[j]) <= C * C + EPS) { mask |= (1 << j); } } if (mask) circles.push_back(mask); }; // 1. 单点圆：圆心放在该点上 for (int i = 0; i < n; ++i) { addCircle(p[i]); } // 2. 两点圆：过两个点、半径为 C 的圆 for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { double dij = sqrt(dist2(p[i], p[j])); if (dij > 2.0 * C + EPS) continue; Point mid((p[i].x + p[j].x) / 2.0, (p[i].y + p[j].y) / 2.0); double h2 = C * C - (dij / 2.0) * (dij / 2.0); if (h2 < 0.0) h2 = 0.0; double h = sqrt(h2); double vx = -(p[j].y - p[i].y) / dij; double vy = (p[j].x - p[i].x) / dij; addCircle(Point(mid.x + vx * h, mid.y + vy * h)); addCircle(Point(mid.x - vx * h, mid.y - vy * h)); } } // 去重，减少 DP 里的无效枚举 sort(circles.begin(), circles.end()); circles.erase(unique(circles.begin(), circles.end()), circles.end()); int full = (1 << n) - 1; vector<int> dp(1 << n, n + 1); dp[0] = 0; for (int mask = 1; mask <= full; ++mask) { int low = __builtin_ctz(mask); for (int cm : circles) { if (cm & (1 << low)) { dp[mask] = min(dp[mask], dp[mask & ~cm] + 1); } } } cout << dp[full] << '\n'; } return 0; }我拿下面这组数据自测过，思路和代码都对得上：
3 2.0 1.0 0.0 0.0 1.0 0.0 2.0 0.0 0这里 R = 2，D = 1，所以 C = 1。三个点 (0,0)、(1,0)、(2,0) 刚好可以被以 (1,0) 为圆心、半径 1 的圆一次盖住，所以输出应该是 1。如果把中间点挪到 (0.5,0)，那么最左边的点和最右边的点距离 2，刚好等于 2C，也能用一个圆盖住；如果距离超过 2C，就必须分开。
5. 浮点数陷阱、边界条件和实测表现
这类题 WA 往往不是思路错，而是精度和边界没处理好。我把自己踩过、见过的坑列一列。
第一是 EPS 到底取多大。坐标和半径一般是实数，但数据范围不大，我习惯用 1e-9。点是否在圆内判断用平方距离：dist2 <= CC + EPS。注意是用平方比较，不要每次都开根号，否则精度损失更大，速度也慢。两点距离是否超过 2C 的判断同理，可以先算 d2，再和 4C*C 比较，但后面算 h2 需要 d，所以开一次根号也说得过去。我的代码里直接用 d 比较，顺手也写了 EPS。
第二是 h2 可能出现微小的负数。两个点距离理论上等于 2C，但浮点算出来可能比 2C 大一点点，导致 h2 是 -1e-15。这时候不要直接 sqrt，先 clamp 成 0。如果不处理，某些编译器上 sqrt(负数) 会返回 NaN，候选圆全部丢失，DP 结果瞬间退化成 N，而且样例这种小数据可能测不出来。
第三是重合点。如果两个点坐标完全相同，dij = 0，垂直向量 vx、vy 计算会除零崩掉。我的处理是跳过 dij ≤ EPS 的情况，靠单点圆去盖它们。因为单点圆规则是“到圆心距离不超过 C”，两个重合点当然会一起被盖上，不会漏。
第四是 C 很大的情况。如果 C 大到能覆盖所有点，dp 自然算出 1。这时候两点圆的枚举依然正确，只是很多两点间距都 ≤ 2C，候选圆数量会比较多。幸好 N 只有 20，多出来的也就是 O(N²) 个，完全能接受。
第五是“有效半径恰好为 0”这个边界。我见过有人把 R - D <= 0 直接输出 0，因为觉得“没有能盖点的圆，所以不用围栏”。这是错的。题目要求的是“最少需要多少个围栏”，不是“最少要盖几个点”。一个圆都保护不了任何树的时候，每棵树都必须分配一个自己的围栏，答案是 N，不是 0。这个特判一定要放在最前面。
至于复杂度，候选圆数量最多是 N + N*(N-1)，也就是 O(N²)。DP 一共 2^N 个状态，每个状态遍历所有候选圆，所以最坏复杂度 O(N²·2^N)。N=20 的时候大约 4 亿次简单位运算，C++ 下实测一两秒钟能跑完。如果你担心多组数据撑不住，可以做一个简单优化：对每个点 i 预先只保留覆盖它的候选圆列表，DP 时只遍历属于 low 点的那份列表，这样常数能压掉很多。
6. 我的排错经历：样例过了却 WA 的三个原因
这道题我一开始没做特判，直接上来算 C，样例也过了，交上去 WA。后来发现是三个看起来很小的问题叠在一起。
第一个问题是 R - D 接近 0 的情况。我当时以为 C 很小也无所谓，反正单点圆还能盖自己。但仔细一想，C 等于 0 的时候，点必须和圆心完全重合才满足条件，而你要放半径为 R 的围栏，圆心又不能无限多，于是每个点都得单独一个围栏。加上这个特判之后，一版就过了。
第二个问题是两个点距离刚好等于 2C。我的第一版代码里判断条件是 dij > 2.0 * C + EPS 就 continue，理论上没问题，但后续 h2 没有 clamp。距离恰好等于 2C 时，实际浮点值经常是 2.0000000001 或者 1.9999999999，前者会让 h2 变成负零点几个 ulp，sqrt 直接产出 NaN，那个圆就没了。对随机数据影响不大，对构造的极限数据就是致命 WA。
第三个问题是我一开始没加单点圆。我当时的想法是“反正过两点的圆枚举了所有可能的最优圆”，结果忽略了“一个点周围 2C 范围内没有其他点时，只能单独用圆”的情况。单独点的最优圆边界上确实只有一个点，我的两点枚举一个都列不出来，DP 结果就永远是 N。把“圆心直接放在点上”这种候选补进去之后，逻辑才真正闭环。
这三个问题都解决之后，我又顺手把候选圆去重，把 DP 里重复遍历同样 mask 的损耗降了下来。实测下来，同样的思路改成其他“最小圆覆盖点集”类题目也完全通用。比如把“鹿能伸 D”改成“信号塔覆盖半径是 C”之类的问题，改动只有模型解释那一层，后面几何和 DP 的代码一个字都不用改。
最后再分享一个做题习惯：这种带几何的状压题，我交之前一定会自己构造三组数据，一是“所有点互相离得很远”，期望答案是 N；二是“所有点挤在一个半径 C 的圆内”，期望答案是 1；三是“两个点距离正好等于 2C 但第三个点刚好在边界上”，用来验证 EPS 和 h2 的 clamp。三组都过，基本就能放心交了。
