407359: GYM102770 G Gliding

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Glidingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Link loves cool challenges, such as shooting arrows through small holes, sliding down a 3000-metre-high snow mountain and playing music with a huge piece of leaf. Now he is trying a new challenge of gliding through a lake without sinking into it.

Link's world is a three-dimensional space, let's define a Cartesian coordinate system $$$(x,y,z)$$$, where $$$z$$$ is the height. The water surface is the plane $$$z=0$$$. Link starts at position $$$(s_x,s_y,0)$$$ and the destination is at $$$(t_x,t_y,0)$$$. He fails the challenge if, at any time, his height $$$z$$$ is strictly less than $$$0 \ (z<0)$$$, which means he has fallen into the water.

In Link's world, unlike Earth, things in the air fall freely with a constant speed of $$$v_f$$$. Under such a fast falling speed Link cannot control his body and will fall down vertically with zero horizontal speed. Luckily, Link has a paraglider to slow down the falling. Once he opens the paraglider, the falling speed becomes $$$v_p$$$ ($$$v_p<v_f$$$) and Link is able to move horizontally in any direction with a speed of at most $$$v_h$$$. Formally, Link's speed in the $$$x$$$ direction $$$v_x$$$ and in the $$$y$$$ direction $$$v_y$$$ should satisfy $$$\sqrt{v_x^2+v_y^2} \leq v_h$$$. Link can close and open the paraglider any number of times, and he can do so at any time.

Even better for Link, there are $$$n+1$$$ strange wind caves in the lake, producing wind blowing upwards that helps Link to go higher. Those wind caves are numbered from $$$0$$$ to $$$n$$$, and are described by the tuples $$$(x_i,y_i,v_i),\ i=0,1,\dots,n$$$. The position of the $$$i$$$-th wind cave is $$$(x_i,y_i,0)$$$, and the speed of its upwards wind is $$$v_i$$$. Link must be on the vertical line $$$[x=x_i,y=y_i]$$$ and his paraglider must be open to be affected by the $$$i$$$-th cave. If Link's paraglider is open while on top of the $$$i$$$-th wind cave, he will rise with speed $$$v_i-v_p$$$ if $$$v_i>v_p$$$, or fall with speed $$$v_p-v_i$$$ if $$$v_p>v_i$$$, or have a zero vertical speed if $$$v_p=v_i$$$. The location where Link starts is the $$$0$$$-th wind cave, which means $$$s_x=x_0, s_y=y_0$$$. Link carefully chooses this location such that $$$v_0>v_p$$$, which means he can rise as high as he wants initially. Therefore, it can be shown that Link can always reach the destination without falling into the lake, given sufficient time.

The time that it takes for Link to open and close the paraglider, and the time it takes to change his speed can be neglected. Link wants to know the minimum time needed to arrive at the destination.

Input

The input contains multiple cases. The first line of the input contains a single positive integer $$$T$$$, the number of cases.

For each case, the first line contains four integers $$$s_x,s_y,t_x,t_y \ (-10^4\le s_x,s_y,t_x,t_y\le 10^4)$$$, describing the coordinates of the starting location and the destination. The second line contains three integers $$$v_f,v_p,v_h(0<v_p<v_f\le 10^4,\ 0<v_h\le 10^4)$$$ denoting the free falling speed, the falling speed with the paraglider open and the maximum horizontal speeed respectively. The third line contains a single positive integer $$$n$$$ ($$$n\le 4000$$$), the number of wind caves excluding the one at the start location. The following $$$n+1$$$ lines each contains three integers $$$x_i,y_i,v_i \ (-10^4\le x_i,y_i\le 10^4,\ 0<v_i\le 10^4,\ i=0,1,\dots,n)$$$, denoting the position of each cave and the speed of its wind. It is guaranteed that no two caves have the same position, and there are no wind caves at the destination location.

It is guaranteed that $$$x_0=s_x,\ y_0=s_y,\ v_0 > v_p$$$ and that the sum of $$$n$$$ over all cases doesn't exceed $$$10^4$$$.

Output

For each case, print a single number in a single line, the minimum time needed to arrive at $$$(t_x,t_y,0)$$$ without falling into the lake. Your answer will be accepted if and only if its absolute or relative error does not exceed $$$10^{-9}$$$.

ExampleInput
2
0 0 3 4
5 4 1
1
0 0 5
3 0 6
0 0 3 4
5 4 1
1
0 0 5
3 0 7
Output
25.000000000000000
24.333333333333332
Note

In the first example, Link opens the paraglider at $$$(0,0,0)$$$ and waits 20 seconds so that he rises to 20 units high. Then he moves straight to $$$(3,4,0)$$$ and it costs 5 seconds to arrive there.

In the second example, Link rises to 12 units high at first and moves straight to (3,0,0), which costs him 15 seconds. Then he rises to 16 units high and moves straight to the destination which costs $$$\frac{28}{3}$$$ seconds.

加入题单

上一题 下一题 算法标签: