← 返回题目列表

AtCoder · geocon2013_d

D. 女巫

中文机器翻译题面 查看原题

問題文

你是一个位于河流和绿色环绕之中,虽小却富饶的王国的魔女。
听说新国王将视察王国后,你决定与伙伴们一起去捣乱。
魔女可以在以自己为中心的圆内散布诅咒。
此外,魔力强大的魔女能够逐渐增大圆的大小。
国王如果走进这个圆内就会受到诅咒,因此必须避开并移动。
让我们求出国王从出发地到目的地以最短路径移动所需的时间。
但是,如果国王无法在不受诅咒的情况下到达目的地时 Impossible 。


入力

输入是按以下格式从标准输入给出的。
Sx Sy Gx Gy V N
W1,x W1,y W1,r W1,v
W2,x W2,y W2,r W2,v
...
WN,x WN,y WN,r WN,v
  • 输入全部以整数形式给出。
  • 第一行是出发地的坐标 Sx Sy 、目的地的坐标 Gx Gy 、国王每分钟移动的距离 V 、魔女的× N 用空格分隔。
  • 从第2行到第N+1行是魔女的坐标 Wi,x Wi,y 国王出发时刻的诅咒日记 Wi,r 诅咒的半径在1分钟内扩展的距离 Wi,v 用空格分隔。
  • 国王出发之后 t 分钟后的诅咒半径是 Wi,r + Wi,v * t 。例如, Wi,r = 1, Wi,v = 2 的情况, 0.5 分钟后的诅咒半径是 2 变为。
  • 诅咒的萝卜会连续增长。
  • 出发地和目的地在国王出发时不在诅咒范围内,也不在边界上。

出力

如果国王无法在不受诅咒的情况下从出发地到达目的地, Impossible就输出
能到达的话,输出国王从出发到目的地所需的最短分钟数。
小数点后几位都可以输出,绝对误差或相对误差的至少一方为10-6如果在以下范围内,则视为正确答案。
但是,在诅咒范围的边界上不会受到诅咒。
此外,即使在国王出发时,任何一个魔女的诅咒萝卜 Wi,r - 10-3 从 Wi,r + 10-3 在范围内发生变化,也不会影响是否能够未受诅咒到达目的地。

制約

  • -1000 ≦ Sx, Sy, Gx, Gy, Wi,x Wi,y ≦ 1000
  • (Sx, Sy) ≠ (Gx, Gy)
  • 1 ≦ V ≦ 100
  • 1 ≦ N ≦ 10
  • 1 ≦ Wi,r ≦ 1000
  • 0 ≦ Wi,v ≦ 100

部分点

本问题分为(1)〜(4)的部分得分,除了上面给出的条件外,还需满足以下条件。

  • (1) 50点 : N = 1 かつ Wi,v = 0
  • (2) 100点 : Wi,v = 0
  • (3) 100点 : Wi,v = 0 または V < Wi,v
  • (4) 150点 : N = 1 かつ 0 < Wi,v < V

入力例 1

0 0 10 10 2 1
5 5 5 0

出力例 1

8.926990817

入力例 2

0 0 10 10 2 2
4 6 4 0
6 4 4 0

出力例 2

9.141592654

入力例 3

0 0 10 10 2 2
4 6 4 0
6 4 4 3

出力例 3

Impossible

入力例 4

22 53 98 32 4 1
69 40 2 1

出力例 4

21.425021992