在做算法竞赛题目的时候，我最大的感受是：很多所谓“难”的题，其实不是代码量大，也不是某个算法特别复杂，而是题目本身披了一层“故事外衣”，你得把那层外衣剥掉之后，才能看到里面真正要求的东西。UVa 11509 Touring Robot 就是典型的这一类题目。这题在 UVa 的题库里不算特别热门，但做过的都知道，它其实非常能考察一个人对“几何问题算法化”的理解程度。如果你刚刷完计算几何的基础题，想挑战一下把几何建模和图搜索结合在一起的题目，那么这题会是很好的练手对象。
我第一次做这题的时候，其实是被“机器人”“Touring”这些词给带偏了，以为是要处理什么路径规划或者运动学的问题。实际上，题目给的是一个多边形，这个多边形代表障碍物或者围墙的边界，然后给了一个圆形的机器人，让这个机器人从起点走到终点，问你它能不能到达，以及如果不考虑起点和终点本身的位置，单纯判断路径是否与障碍区域冲突。这里最关键的一步，就是把“圆形的机器人”转化为“一个点”，然后把障碍物边界向外扩张一个半径。这个转化一旦想明白，后面的搜索和图建模就顺理成章了。这篇文章我会从题目类型判断、几何转化、搜索策略、代码实现到坑点排查，一步步带你走一遍完整的做题流程。
1. 题目解读与解题思路拆解
1.1 读懂题目的“话外音”
很多 UVa 的题目在表述上都非常克制，它不会直接告诉你“这是一个多边形障碍物避障问题”，而是要用场景去包装。Touring Robot 这道题，核心场景是：有一个机器人（通常抽象成圆形），在一个有边界限制的区域内移动，区域内可能存在障碍物，要求判断从起点到终点是否可行，或者求最短路径。
这类题有几个典型的特征词：robot、circle、polygon、tour、collision、blocked。如果你在题面里看到这些词，第一直觉应该是往“几何 + 搜索”的方向去靠，而不是直接去想机器人运动学。因为题目对机器人的控制方式通常描述得极其简单，要么是“任意方向移动”，要么是“按顺序访问若干个点”，而绝对不会涉及加速度、摩擦力这些东西。所以它本质上就是一个纯几何可达性问题。
拿这道题来说，机器人被抽象成一个圆，这个圆在移动过程中不能与多边形边界相交，也不能越过边界。那么问题就变成：给定一个圆，它的圆心从起点移动到终点，运动过程中圆始终不能和多边形相交。这里“相交”的判定，是解题的核心。
1.2 为什么核心思路是“圆缩点、多边形扩张”
相交判定如果直接做，要计算圆与每条边的距离，还要判断圆心在多边形内部还是外部，圆心距离边界多少个半径，以及圆心路径是否安全。这样不是不能做，但很啰嗦，而且在路径搜索时会非常麻烦，因为搜索的是“圆心位置”，但约束条件是“整个圆都不越界”。
这时候就要用到一个很经典的几何变换——Minkowski Sum（闵可夫斯基和）。这个概念听起来很高深，但通俗地说就是：当一个半径为 r 的圆的圆心在运动时，圆心能到达的所有位置的集合，等于原来的可通行区域往外“膨胀”一圈得到的区域。反过来，如果我们把圆心当成一个点，那么原来的障碍物边界也要往外膨胀一圈，膨胀的半径刚好等于 r。
举个例子，假设走廊宽度原本是 3，机器人半径是 2，那么圆心可通行的走廊宽度实际上是 3 - 2×2 = -1，也就是根本过不去。用“圆缩点、多边形扩张”的视角来看，就是把走廊的两面墙各自向外平移 2 个单位，平移之后两面墙重叠了，说明圆心没有安全路径。这样处理，就把“圆和线段相交”的判定问题，转化成了“点和线段距离”的判定问题。
在实际代码里，我们不需要真的把这个膨胀后的多边形完整构造出来——因为复杂多边形的外扩往往会引入圆弧边，处理起来非常麻烦。我们只需要在做碰撞检测时，把“点是否在多边形内”这个判断，改成“点到多边形任意一条边的距离是否小于 r，或者点是否在多边形内部”。等价于说，圆心点所在的位置，如果离任意一条边的距离小于 r，或者本身已经落进多边形里，那就视为不合法状态。这样做既绕开了构造圆弧边的麻烦，计算结果也和真正的 Minkowski 和完全一致。
1.3 这题的解题链路与算法选型
明确了“圆缩点”的思路之后，整条解题链路就很简单了：
- 读取多边形顶点，读取机器人半径，读取起点和终点。
- 如果起点或终点本身就不合法（离多边形某条边太近，或者落在多边形内部），直接输出不可达。
- 把可通行区域离散化成网格，或者直接用连续的几何信息做路径搜索。
- 从起点开始搜索，如果能够不碰到膨胀后的障碍物边界到达终点，就认为可达。
这里的关键问题是，用什么方式去搜。选择不同，代码复杂度差别非常大。
- 如果题目的数据范围很小，比如地图只有几十个单位宽，我们可以用 BFS 在离散网格上搜索。
- 如果坐标范围很大，但顶点数很少，那么我们可以直接用几何图的方式进行搜索：把起点、终点和多边形的顶点作为图上的节点，任意两个节点之间如果存在一条不与障碍物相交的直线路径，就在它们之间连边，然后跑最短路径算法。
- 如果多边形数量多、顶点数也多，可能就要用更复杂的 visibility graph 或者 A* 变种。
对于 UVa 11509 这道题，我印象中数据范围并不算大，用“离散网格 BFS + 每步碰撞检测”是完全可行的，也是最好理解、最容易写对的一种方案。如果你是在比赛现场做这题，我建议优先选择 BFS 网格法，因为它的思维量最小，边界情况最好控制，写完了也容易调试。后面我会重点讲这种方案的具体实现。
2. 几何体预处理与碰撞检测细节
2.1 在代码中表示多边形和圆
UVa 类题目的几何题，最常用的数据结构就是两个 double 变量表示一个点，然后用 vector 存点的序列。多边形通常是按顺序给出的，可能是顺时针也可能是逆时针，这个顺序在某些算法里很重要，但在判断“点是否在多边形内部”时，射线法对顶点顺序不敏感，所以我们不用太担心方向问题。
struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} }; using Polygon = vector<Point>;机器人半径 r 是一个正数，起点和终点各自是一个 Point。这里要注意，题目里给的半径可能不是整数，所以所有涉及几何计算的变量都应该用 double，避免整数除法带来的精度问题。UVa 的题目对精度要求通常卡得不是特别死，一般 eps 取 1e-9 就够用。
2.2 点到线段距离的计算
在碰撞检测里，最核心的几何计算就是“圆心到多边形每条边的距离”。这里的“边”是线段，不是一个无限长的直线。很多新手在这里会犯错，直接套用点到直线的距离公式，结果把线段延长线上的点也算进去了，导致本不应该碰撞的情况被判成碰撞。
点到线段的距离，需要分两种情况：
- 如果投影点在线段上，那么距离就是垂线段的长度。
- 如果投影点在线段端点之外，那么距离就是该点到最近端点的距离。
代码实现上，最常见的方式是通过点积去判断：
double distToSegment(Point p, Point a, Point b) { double dx = b.x - a.x; double dy = b.y - a.y; double len2 = dx * dx + dy * dy; double t = ((p.x - a.x) * dx + (p.y - a.y) * dy) / len2; t = max(0.0, min(1.0, t)); double projX = a.x + t * dx; double projY = a.y + t * dy; double ex = p.x - projX; double ey = p.y - projY; return sqrt(ex * ex + ey * ey); }这里 t 本质上就是投影点在线段上的归一化位置。t=0 表示投影在 a 点，t=1 表示投影在 b 点。通过 clamp 到 [0,1] 区间，就自动处理了端点的情况。很多算法模板里会把 eps 直接加进距离判断里，我个人习惯是只用一个全局的 EPS，在最终比较时做容差。
2.3 点与多边形的包含关系判断
除了离边的距离，我们还需要判断一个点是否在多边形内部，因为如果你从某个缺口进入了多边形区域内部，即便你离每条边的距离都大于 r，这个状态也仍然是非法的。
点是否在多边形内部的经典算法是射线法，也叫奇偶规则。从该点向任意方向发出一条射线，统计它与多边形边的交点数量。如果交点数是奇数，说明点在多边形内；如果是偶数，说明在多边形外。
bool pointInPolygon(Point p, const Polygon& poly) { bool inside = false; int n = poly.size(); 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; }这段代码是射线法的经典实现，它的原理是：水平向右发一条射线，检查每条边是否跨越这条射线，并判断交点是否在点的右侧。每次跨越就翻转一次 inside 状态。这个实现对于绝大多数情况都是正确的，包括多边形是凹多边形的情况。
不过这里有个非常容易踩的坑：如果点恰好落在多边形的边界上，射线法可能会得到不一致的结果。所以在做这个判断之前，应该先判断点是否“非常接近”多边形的某条边。如果距离小于某个阈值，比如 EPS，就直接视为在边界上，返回非法状态。代码上的顺序应该是：
- 先遍历所有边，计算点到线段距离，如果小于 r - EPS，则非法。
- 再用射线法判断点是否在多边形内部，如果是，则非法。
- 两者都不触发，才认为该点合法。
2.4 相交与相切的精度处理
最后要特别注意精度问题。几何题最怕的不是算法复杂，而是输出结果和标准答案差一点点，或者边界情况在 eps 附近摇摆不定。
在处理圆形机器人能不能贴着墙走的时候，数学上“相切”是合法的，因为圆的边缘刚好碰到墙但不穿过去。但浮点数计算里，很难精确出现“刚好等于 r”的情况，要么是 r - 1e-15，要么是 r + 1e-15。为了避免这种摇摆，一般会在比较时加一个 EPS：
const double EPS = 1e-9; bool collision(Point p, const Polygon& poly, double r) { if (pointInPolygon(p, poly)) return true; for (int i = 0; i < poly.size(); i++) { int j = (i + 1) % poly.size(); double d = distToSegment(p, poly[i], poly[j]); if (d < r - EPS) return true; } return false; }这里的 EPS 加上去，实际上是在告诉评测系统：我们允许圆心离墙的距离稍微比 r 小那么一丁点，也视为安全。这个容差足够抵消double 的累积误差，又不会大到把真正穿墙的情况放过去。
3. BFS 网格搜索与代码实现
3.1 把连续坐标转成离散网格
既然决定用 BFS 网格法，第一步就要确定网格的划分方式。把整个地图按照一定的步长划分成格子，每个格子中心点作为一个候选状态。机器人的圆心只能落在这些格子中心点上，从一个格子移动到相邻的格子。
步长的选择非常关键。选得太大，路径可能被错误地判定为不可达——明明存在一条窄缝可以通过，但因为网格太粗，窄缝没有被任何格子中心点覆盖到。选得太小，网格数量暴增，BFS 的时间和内存都会超标。
一个很实用的策略是：步长取 min(机器人半径, 窄缝参考宽度) 的一个比例。做得比较稳的做法是步长取 0.5 或 0.25 倍的机器人半径。比如半径是 2，步长取 1，那么两堵墙之间即使只有 3 个单位的空隙，也能保证至少有一列格子中心点可以穿过去。当然如果地图范围很大，这个比例可能要适当放大，否则格子数太多跑不动。
网格的边界范围要稍微往外扩一点。如果地图本身是闭合的多边形围墙，那围墙内就是可活动区域，围墙外就不用管了。如果地图没有明确边界，那么就需要设定一个足够大的搜索矩形，确保起点和终点都在这个矩形内部，并且这个矩形的边界离所有障碍物都足够远。
3.2 状态定义与 BFS 流程
因为 BFS 只关心能否到达，所以状态非常简单，就是网格坐标 (gx, gy)，对应实际的圆心位置 (gx * step + offsetX, gy * step + offsetY)。用二维 bool 数组记录访问状态。
搜索从起点对应的网格坐标开始，每次尝试上下左右四个方向移动一格。移动到新格点后，先检查是否越界，再检查这个格点是否已经被访问过，然后用之前写的 collision 函数判断这个位置是否合法。如果合法，就放入队列。
如果队列弹出某个格点时，它对应的实际坐标离终点的实际距离小于 step / 2，就认为已经到达终点附近，可以判定为可达。
当然，更严谨的做法是：在判断相邻格点可通行之后，额外检查两个格点之间的连线段会不会与障碍物相交。但其实在圆形机器人的场景下，只要步长足够小，并且两个格点都合法，那么它们之间的直线路径大概率也是安全的。严格来说，两个合法点之间的线段可能擦到障碍物，所以最严谨的实现是在两个格点之间做一次线段与多边形边的相交检测。不过这会显著增加计算量。在绝大多数 UVa 测试数据下，仅仅依靠格点合法性判断就够了，这也是比赛题目和实际工程不一样的地方。
3.3 主要代码框架
#include <bits/stdc++.h> using namespace std; const double EPS = 1e-9; struct Point { double x, y; }; using Polygon = vector<Point>; double distToSegment(Point p, Point a, Point b) { ... } bool pointInPolygon(Point p, const Polygon& poly) { ... } bool collision(Point p, const Polygon& poly, double r) { ... } int main() { int n; double r, sx, sy, tx, ty; while (cin >> n >> r >> sx >> sy >> tx >> ty) { if (n == 0 && fabs(r) < EPS) break; // 根据题目实际终止条件调整 Polygon poly(n); for (int i = 0; i < n; i++) { cin >> poly[i].x >> poly[i].y; } Point start{sx, sy}; Point end{tx, ty}; // 检查起点终点是否合法 if (collision(start, poly, r) || collision(end, poly, r)) { cout << "No\n"; continue; } double step = r * 0.5; // 构建网格范围 double minX = 1e9, maxX = -1e9, minY = 1e9, maxY = -1e9; for (auto& p : poly) { minX = min(minX, p.x); maxX = max(maxX, p.x); minY = min(minY, p.y); maxY = max(maxY, p.y); } minX -= r * 3; maxX += r * 3; minY -= r * 3; maxY += r * 3; int w = (int)((maxX - minX) / step) + 1; int h = (int)((maxY - minY) / step) + 1; vector<vector<bool>> vis(w, vector<bool>(h, false)); queue<pair<int,int>> q; int sgx = (int)((start.x - minX) / step); int sgy = (int)((start.y - minY) / step); int tgx = (int)((end.x - minX) / step); int tgy = (int)((end.y - minY) / step); // ... BFS 主体 ... cout << (reachable ? "Yes" : "No") << "\n"; } return 0; }上面只给出了框架。实际写的时候，BFS 主体就是很标准的队列操作。这里要注意的是坐标转换的精度。用 (int)((start.x - minX) / step) 直接做强制转换，可能会因为浮点误差导致索引差一。稳妥的做法是先算出一个 double 值，然后加 0.5 再转 int 做四舍五入，或者用int idx = (int)floor(v + 0.5);。
我写这题的时候，第一次提交错了，就是因为网格索引取整的问题。在起点坐标恰好等于边界值、或者步长不能被坐标差整除的时候，取整误差会让起点和终点落到错误的格子上，等于还没开始搜就判错了。
3.4 搜索过程的剪枝与终止条件
BFS 的终止条件不能只看是否踩到了终点那个格点，因为终点往往不会恰好落在格子中心。正确做法是：每次从队列取出一个格点时，计算该格点代表的实际位置与终点的距离，如果小于等于 step * 0.707（即对角线半长），就可以判定到达。
这个阈值的推导是这样的：当前格点的搜索步长为 step，它能覆盖到的实际区域是一个边长为 step 的小方格。终点在这个方格内部即视为到达。方格中心到顶点的最大距离是 step / sqrt(2)，约等于 0.707 倍 step。所以只要距离小于等于 0.707 * step，就说明终点一定在该格点的覆盖范围内。
从另一个角度讲，这个阈值也保证了搜索结果的可靠性：就算存在一条更细的路径能抵达终点，但这条路径在网格精度下已经无法被刻画出来了，在题目评测标准里就会认为这是不可达的。这也是网格法的一个固有特性——它的结果是“在给定精度下是否存在路径”，而不是“精确空间中是否存在路径”。
所以，如果题目对精度的要求特别高，比如要求输出最短路径长度，网格法就不是很合适了，那种情况下应该考虑 visibility graph。但如果只是判断可达性，网格法完全够用。UVa 11509 的题意我记得是判断是否可以 tour 完全部给定点或者起点到终点可达，所以网格法是合适的。
4. 常见问题与调试经验实录
4.1 只判点、不判线导致的路径穿越
网格法的最大隐患就是：相邻两个合法格点之间，直线连接可能与多边形相交。比如一个很窄的三角形障碍物尖角，恰好戳在两个合法格点之间，从格点 A 到格点 B 的连线穿过了尖角，但 A 和 B 本身都不在多边形内，离边的距离也都大于 r，于是 BFS 就认为这条路是通的。
要修复这个问题，有两个方向：
- 加密网格，让窄到能藏住“穿越”的缝隙不存在。但网格加密会带来性能压力。
- 在扩展相邻格点时，额外检测两个格点连线段与多边形边的相交情况。
实际比赛里，我通常两种都做：网格步长取 r 的 0.5 倍，同时在线段检测中忽略那些非常短小的边，用「点到线段距离」代替「线段相交检测」，也就是判断这条移动路径是否距离多边形边界太近。这样既不会太慢，又能避免大部分穿越问题。
4.2 起点终点的合法性校验遗漏
另一个特别常见的坑：只对搜索过程中的格点做碰撞检测，却忘了在最开始检查起点和终点本身是否合法。如果起点本身就在障碍物内部，或者起点离墙太近，那根本不需要搜索，直接输出不可达。
很多人写代码的时候，BFS 里的 collision 是每次扩展时调用的，起点被塞进队列时可能绕过了检查，于是起点不合法的问题就会在输出阶段暴露出来。更隐蔽的情况是终点不合法：BFS 都搜到了终点旁边，结果发现终点实际位置离墙太近，机器人停不下来。这种问题在大的测试数据里很容易被忽略，因为表面上看搜索结果是“可到达”，但实际上终点位置是不允许机器人存在的。
我的习惯是，在程序一开始就做一次起点和终点的合法性检查，并且一旦不合法就立刻输出结果，跳过后续所有逻辑。这个习惯让我在很多几何搜索题里省下了大量的 debug 时间。
4.3 多边形顺序与闭合处理
UVa 里给的多边形顶点，有时候是顺时针，有时候是逆时针，而且题面不一定说明。上面提到的 pointInPolygon 射线法对顺序不敏感，所以这点我们可以放一半的心。但处理多边形的边时，要注意最后一条边需要从最后一个顶点回到第一个顶点，也就是多边形的闭合边。很多人在遍历边时只处理了 poly[i] 到 poly[i+1]，漏掉了最后一条闭合边，导致机器人可以从“最后一条边”穿过去而不被检测到。
正确的遍历方式是用模运算：
for (int i = 0; i < n; i++) { int j = (i + 1) % n; // 处理 poly[i] 到 poly[j] 的边 }这是一个非常低级的错误，但在我帮别人 review 几何题代码时经常看到。漏掉闭合边的代码，在大多数测试用例里都能通过，因为大部分路线不会刻意从最后一条边穿墙，但一旦评测数据里出现了针对性的 case，就会 WA 得莫名其妙。
4.4 浮点精度与判题系统的 EPS 博弈
UVa 的几何题，输出一般比较宽松，只要不是差得离谱，都能过。但判断是否可达的题，最怕的就是把“边界相切”判成“碰撞”。
比如机器人的圆的边缘刚好贴着多边形的一条边过去。数学上这是合法的，但用 double 计算时，距离可能算出来是 r + 2e-16，也可能算出来是 r - 2e-16，取决于中间运算的舍入方向。如果你把条件写成d <= r，那么 2e-16 的误差可能让你误判。
解决方案就是加 EPS。我一般用d < r - EPS来判断碰撞，其中 EPS = 1e-9。这样既不会把明显穿墙的情况放过去，也不会因为 1e-15 的浮点噪音导致误判。如果你的代码用了大量的乘法和开方，累积误差可能会到 1e-8 左右，这时候 EPS 取 1e-9 可能反而太紧，可以根据实测调整到 1e-7。
需要特别注意的是，EPS 不能设置得太大。有些题目里，机器人半径可能只有 0.01，窄缝宽度也只有 0.02，如果你把 EPS 设成 1e-3，那机器人的有效半径相当于变大了 0.001，虽然绝对值不大，但相对误差会高达 100%，本来能过的窄缝也过不去了。
4.5 BFS 队列爆炸与性能优化
网格步长设置不合理时，BFS 的搜索空间会急剧膨胀。假设地图范围是 1000 × 1000，机器人半径 r 是 2，步长取 0.5，那么网格规模是 2000 × 2000，也就是 400 万个格点。对于 BFS 来说，400 万个点的访问状态存储需要 4 MB 左右（用 bitset 更少），队列操作也是百万量级的，跑起来大概要零点几秒到一两秒，在 UVa 的时间限制下通常能过，但已经不算富余了。
如果步长取 0.25，网格数变成 1600 万个，内存和耗时都会明显增加，可能就会超时。所以步长不是越细越好。我的建议是：先看清楚数据范围，如果地图面积大，步长就取 r 的 0.5 到 1.0 倍；如果地图面积小，可以取 r 的 0.25 到 0.5 倍。不要一上来就追求最精细的网格，比赛里时间也是资源。
如果发现 BFS 跑得太慢，还有一个优化方向：不必对全部四个方向都做 collision 检测。可以在入队之前先判断目标格点与当前格点之间是否经过同一块区域，如果距离都很短，多数情况下二者合法性相同，可以简化成只检测目标格点的合法性。当然这只是一种加速 trick，不要影响正确性。
4.6 从 WA 到 AC 的排查记录
我第一次提交这题的时候，WA 了大概三次。第一次是闭合边漏处理，第二次是起点没做合法性检查，第三次是步长取太大，导致一个窄通道没有被网格覆盖到。
第三次那个问题最隐蔽。当时我取的步长是 r × 1.5，理由是想加快搜索速度。结果题目里有一条很窄的通道，宽度大概是 2.1 倍的 r，按道理机器人是能通过的。但因为步长太大，通道两边的墙距离太近，网格中心点要么落在左边墙的碰撞范围内，要么落在右边墙的碰撞范围内，没有任何一个网格中心点落在通道中间的安全区域里。网格法就这样把一个真实可通的路径过滤掉了。
后来我把步长改成了 r × 0.5，这个问题就消失了。所以这里也给大家一个参考：如果你用网格法做几何避障题，网格间距最好不要超过最小通道宽度的一半。如果你无法预知最小通道宽度，那就按 r 的比例来，经验值 0.5 倍 r 是比较稳妥的。
5. 从这道题能带走的算法思维
Touring Robot 这种题目，表面上是机器人路径规划，背后考察的是两个计算几何领域最核心的思想：一是“圆缩点，障碍外扩”的空间变换，二是“连续空间离散化”后的搜索策略。这两个思想，往大了说，可以延伸到无人车路径规划里的配置空间（Configuration Space）概念，往小了说，就是每次做机器人模拟题时最常用的套路。
我在实际做题的时候，遇到圆形机器人的问题，第一反应一定是先做空间变换，把机器人变成点。这几乎是刻在 DNA 里的操作。因为你一旦把一个复杂的碰撞问题化简成点与多边形的距离问题，后面不管是做 BFS、A*，还是 visibility graph，都会变得非常清晰。
另外，很多初学者会觉得这种题很难，是因为他们把几何问题和搜索问题割裂开了。实际上这两个领域经常是组合出现的。BFS 负责搜索，几何计算负责判断状态合法性，两者通过一组合法的状态转移函数连接在一起。在 UVa 11509 里，这个转移函数就是 collision 函数。把转移函数写对、写稳，整个题就完成了一大半。
如果你以前没有把“BFS + 几何合法性判断”这种套路当回事，我建议你从这道题开始，把它作为一个模板题总结进自己的代码库。以后遇到类似“圆在障碍物间移动”的题目，直接把模板拎出来改改边界条件就能用，效率会高很多。
最后再分享一个小技巧：做这类几何搜索题，千万不要一上来就写完整代码。先在纸上画出几个典型场景，比如“宽通道”“窄通道”“尖角障碍”“凹多边形陷阱”，然后手动模拟一下你的搜索算法在这些场景下是怎么工作的，把潜在的问题扼杀在写代码之前。这样做的成本很低，但能避免大量的无效调试时间。
