P2452

i_am_not_feyn · 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 圆，故而不会出现只会包含一条边的情况，必定不穿过。

圆弧是否穿过圆内部

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

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

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