🧠 题解（Solution）

✅ 本质分析

本题是一个典型的几何最短路径问题，带有障碍物（树木）的限制。我们可以将其抽象为带障碍的最短路径求解，路径不能穿过任意树的圆形范围。

🔍 问题抽象

卢克的起点是 $(x_0, y_0)$；

终点是 $(x_t, y_t)$；

每一棵树是一个圆形障碍物（有中心和半径）；

卢克不能穿过树的圆形区域；

他可以绕树走，但只能绕着树的边缘或从树与树之间的可达区域穿过；

求的是从起点到终点的最短路径，然后根据速度计算时间。

✏️ 步骤概览（核心思路）

图模型构建：

点集包括：起点、终点、每棵树的圆周上的若干采样点（可以采样成圆上的 $n$ 个点）；

若两个点之间连线不穿越任意树的圆形区域，则可建边；

这些边的权重是欧几里得距离。

最短路径搜索：

用 Dijkstra 或 A* 算法在图中求从起点到终点的最短路径；

计算时间：

飞行速度为 $v = 200$ 英里/小时；

时间计算公式：

𝑡

𝑑 200 × 3600 ( 单位为秒 ) t= 200 d ​ ×3600(单位为秒)

🧮 样例解析

在样例中：

有两棵树，其中心为 $(4.0, 0.0)$ 和 $(6.0, 0.0)$，直径均为 $1.0$；

卢克从 $(0.0, 0.0)$ 到 $(10.0, 0.0)$；

由于不能穿过树，需要绕着树走；

绕行后最短路径长度为约 $10.0635$ 英里；

所以时间约为：

10.0635 200 × 3600 ≈ 181.13    秒 200 10.0635 ​ ×3600≈181.13秒

✅ 总结

类型：几何图最短路径 + 圆形障碍绕行问题；

关键点在于构图：将障碍区域转化为图中的点和边；

可以通过构造可达的点集合+验证直线段是否与任意圆相交判断可连通性；

距离除以速度后换算单位即可。

代码实现