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