AT_geocon2013_d 魔女

你是一位生活在被河流与绿地环绕的小而富饶王国里的魔女。 你听说新国王要巡视王国，于是决定和同伴们一起去捣乱。 魔女可以以自身为圆心，在圆的内部散布诅咒。 魔力强大的魔女还能让这个圆的半径逐渐变大。 国王如果进入这些圆的范围就会受到诅咒，因此必须避开这些区域前进。 请你计算国王从出发地到目的地最短需要多少时间。 如果国王无法在不受诅咒的情况下到达目的地，则输出 `Impossible`。 输入按如下格式从标准输入给出： $ Sx\ Sy\ Gx\ Gy\ V\ N $ $ W1,x\ W1,y\ W1,r\ W1,v $ $ W2,x\ W2,y\ W2,r\ W2,v $ $ \cdots $ $ WN,x\ WN,y\ WN,r\ WN,v $ - 所有输入均为整数。 - 第 1 行给出出发地坐标 $ Sx\ Sy $，目的地坐标 $ Gx\ Gy $，国王每分钟移动的距离 $ V $，魔女人数 $ N $，各项以空格分隔。 - 第 2 行到第 $N+1$ 行，每行给出一位魔女的坐标 $ Wi,x\ Wi,y $，国王出发时的诅咒半径 $ Wi,r $，以及诅咒半径每分钟扩大的距离 $ Wi,v $，各项以空格分隔。 - 国王出发 $ t $ 分钟后，第 $i$ 位魔女的诅咒半径为 $ Wi,r + Wi,v \times t $。例如，$ Wi,r = 1,\ Wi,v = 2 $ 时，$ 0.5 $ 分钟后诅咒半径为 $ 2 $。 - 诅咒半径是连续变化的。 - 出发地和目的地在国王出发时都不在任何诅咒范围内，也不在边界上。 如果国王无法在不受诅咒的情况下从出发地到达目的地，输出 `Impossible`。 如果可以到达，则输出国王从出发到到达目的地所需的最短时间。 小数点后任意位数均可，只要绝对误差或相对误差至少有一项不超过 $10^{-6}$ 即视为正确。 注意，诅咒范围的边界上不会受到诅咒。 另外，如果出发时任意魔女的诅咒半径在 $ Wi,r - 10^{-3} $ 到 $ Wi,r + 10^{-3} $ 之间变化，是否能安全到达目的地的判定不会改变。 - $ -1000 \leq Sx, Sy, Gx, Gy, Wi,x, Wi,y \leq 1000 $ - $ (Sx, Sy) \neq (Gx, Gy) $ - $ 1 \leq V \leq 100 $ - $ 1 \leq N \leq 10 $ - $ 1 \leq Wi,r \leq 1000 $ - $ 0 \leq Wi,v \leq 100 $ 本题分为 (1)～(4) 四个部分分数，除上述条件外还需满足以下条件： - (1) 50分：$ N = 1 $ 且 $ Wi,v = 0 $ - (2) 100分：$ Wi,v = 0 $ - (3) 100分：$ Wi,v = 0 $ 或 $ Vi,v $ - (4) 150分：$ N = 1 $ 且 $ 0 < i,v $

第 1 行：$ Sx\ Sy\ Gx\ Gy\ V\ N $ 第 2 行到第 $N+1$ 行：$ Wi,x\ Wi,y\ Wi,r\ Wi,v $

如果无法安全到达目的地，输出一行 `Impossible`。 否则，输出一行表示最短所需时间的实数，允许任意小数位数，绝对误差或相对误差至少有一项不超过 $10^{-6}$。

由 ChatGPT 4.1 翻译