自动搬运

查看原文

来自洛谷，原作者为

	i_am_not_feyn 志士幽人莫怨嗟，古来材大难为用

搬运于2025-08-24 21:37:50，当前版本为作者最后更新于2023-11-28 10:17:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

计算几何绝世好题 因为现在没人出算几了。

本题给出若干个正方形障碍以及一个圆，求把圆推到目标位置的最短距离。

首先可以把这些障碍向外扩张 $r$，形成一个类似

的图形，拆解开来就是 4 个圆加上俩矩形，将题意转化为从起点出发不穿过任意障碍到达终点的最短路。

先把样例画出来：

发现实际上可能走的路径分为四类：

1. 点到圆上的切点
2. 点直接到另一点
3. 同一圆上的点相互走
4. 圆到另一圆上的点

其中第 4 类实际上就是找到一条线段同时切两个圆，如下图的 $CD$ 以及 $FG$。

可以发现 $AC\perp AB$。

令 $AB$ 中点为 $O$，那么有 $FO$ 切圆 $A$ 于 $F$、$GO$ 切圆 $B$ 于 $G$，套用 1 的方法即可找到 $FG$。

将所有的可能路径都 check 一遍，建出图跑最短路即可。要 check 的是一个线段或者一段圆弧是否穿过某个障碍。

线段是否穿过矩形内部

首先特判掉线段端点在矩形内部以及线段与矩形某条边重合的情况，然后再算出该线段与矩形四条边的交点个数 $x$，当 $x=2$ 时线段穿过矩形。

线段是否穿过圆内部

求出线段到圆心的距离与半径比较一下即可。

圆弧是否穿过矩形内部

这个得画一画。令圆弧端点为 $l,r$（逆时针），称一个点是合法的当且仅当该点不在 $\overrightarrow{ol}$ 和 $\overrightarrow{or}$ 组成的角内。

首先把圆弧上的端点在矩形内部特判掉，按照矩形端点在圆内部的点数 $m$ 以及圆心是否在矩形内部分讨。

• 圆心在矩形内部

  若有一个端点不在圆内部或圆上且该端点不合法，则圆弧穿过矩形内部。

• $m=4$

  圆包含了矩形，肯定不穿过。

• $m=1$

  

  当 $L_1$ 不合法时圆弧穿过矩形。

• $m=2$

  

  当上面两个点有一个不合法时圆弧穿过矩形。

• $m=3$

  

  剩下的那个点不合法就穿过。

• $m=0$

  由于只会出现 $\dfrac 14$ 圆，故而不会出现只会包含一条边的情况，必定不穿过。

圆弧是否穿过圆内部

还是先特判两圆相离、圆弧端点在圆内的情况，若此时另一圆的圆心不合法则穿过。

这个部分尽管比较复杂，但是有大量的重复内容，写起来比较简单，之后就是无脑连边了。

代码太长，丢剪切板上了。