409692: GYM103687 G Easy Glide

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

Description

G. Easy Glidetime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

Grammy is playing a boring racing game named Easy Gliding. The game's main content is to reach the destination as fast as possible by walking or gliding. The fastest player wins.

Each player controls a character on a two-dimensional plane. A character can walk at any moment with a speed of $$$V_1$$$. Especially, when a character touches a gliding point, he/she can glide with a speed of $$$V_2$$$ for the following $$$3$$$ seconds. It is guaranteed that $$$V_1 < V_2$$$.

Now Grammy locates at point $$$S$$$ and she knows the coordinates of all the gliding points $$$p_1, p_2, \dots, p_n$$$. The goal is to reach point $$$T$$$ as fast as possible. Could you tell her the minimum time she has to spend to reach point $$$T$$$?

Input

The first line contains one integer $$$n$$$ ($$$1\leq n\leq 1\,000$$$), denoting the number of gliding points.

The following $$$n$$$ lines describe the gliding points. The $$$i$$$-th line contains two integers $$$x_i,y_i$$$ ($$$-1\,000\,000 \leq x_i,y_i \leq 1\,000\,000$$$), representing the coordinates of the $$$i$$$-th gliding point $$$p_i$$$.

The next line contains four integers $$$S_x,S_y,T_x,T_y$$$ ($$$-1\,000\,000 \leq S_x,S_y,T_x,T_y \leq 1\,000\,000$$$), representing the coordinates of $$$S$$$ and $$$T$$$.

The next line contains two integers $$$V_1, V_2$$$ ($$$1\leq V_1 < V_2 \leq 1\,000\,000$$$), representing the speed of walking and gliding.

Output

Output the minimum time Grammy has to spend to reach point $$$T$$$ in one line. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

ExamplesInput
2
2 1
0 3
0 0 4 0
10 11
Output
0.400000000000
Input
2
2 1
-2 0
0 0 4 0
1 2
Output
3.354101966250
Input
2
2 1
-2 0
0 0 4 0
1 10000
Output
2.000600000000

加入题单

上一题 下一题 算法标签: