G - Easy Glide

SDUT 2022 Spring Team Contest(for 21) - 12 - Virtual Judge

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_1V1​. Especially, when a character touches a gliding point, he/she can glide with a speed of V_2V2​ for the following 33 seconds. It is guaranteed that V_1 < V_2V1​

Now Grammy locates at point SS and she knows the coordinates of all the gliding points p_1, p_2, dots, p_np1​,p2​,…,pn​. The goal is to reach point TT as fast as possible. Could you tell her the minimum time she has to spend to reach point TT?

Input

The first line contains one integer nn (1leq nleq 1,0001≤n≤1000), denoting the number of gliding points.

The following nn lines describe the gliding points. The ii-th line contains two integers x_i,y_ixi​,yi​ (-1,000,000 leq x_i,y_i leq 1,000,000−1000000≤xi​,yi​≤1000000), representing the coordinates of the ii-th gliding point p_ipi​.

The next line contains four integers S_x,S_y,T_x,T_ySx​,Sy​,Tx​,Ty​ (-1,000,000 leq S_x,S_y,T_x,T_y leq 1,000,000−1000000≤Sx​,Sy​,Tx​,Ty​≤1000000), representing the coordinates of SS and TT.

The next line contains two integers V_1, V_2V1​,V2​ (1leq V_1 < V_2 leq 1,000,0001≤V1​

Output

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

Sample 1

2
2 1
0 3
0 0 4 0
10 11

0.400000000000

Sample 2

2
2 1
-2 0
0 0 4 0
1 2

3.354101966250

Sample 3

2
2 1
-2 0
0 0 4 0
1 10000

2.000600000000

#include
using namespace std;
#define int long long
const int N=1010;
double g[N][N];
double dist[N];
bool st[N];
int a[N],b[N];
int n;
int x1,yy1,x2,y2;
int v1,v2;
double f(int x1,int y1,int x2,int y2)//计算两点之间的距离
{
    double ans=0;
    ans=sqrt((x1-x2)*(x1-x2)*1.0+(y1-y2)*(y1-y2)*1.0);
    return ans;
}
double dij()
{
    for(int i=1;i<=n;i++)dist[i]=1e18;
    dist[1]=0;
    for(int i=0;idist[j]))t=j;
        }
        st[t]=1;
        for(int j=1;j<=n;j++)
        {
            if(dist[t]+g[t][j] 
这题看起来很难，其实就是最短路，先求出起点到终点，起点到每个滑翔点，各个滑翔点之间，每个滑翔点到终点之间的距离，现在就变成一个典型的最短路问题，直接dijkstra算法解决问题。