1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<vector> 7 #include<cstdio> 8 #include<stack> 9 #include<queue>10 #include<cmath>11 #include<map>12 #include<set>13 using namespace std;14 const int N=512,M=0x3f3f3f3f;15 const double DIF=1e4;16 struct node{17     int x,y,cost;18 }ap[N];19 int n,air,sx,tx,apn,res=M,dis[N];20 inline int dist(int x,int y){21     return (int)(sqrt((double)((ap[x].x-ap[y].x)*(ap[x].x-ap[y].x)+(ap[x].y-ap[y].y)*(ap[x].y-ap[y].y)))*DIF);22 }23 int main(){24     int T;cin>>T;25     while(T--){26         res=M;27         memset(dis,0x3f,sizeof dis);28         memset(ap,0,sizeof ap);29         30         cin>>n>>air>>sx>>tx;sx--;tx--;31         32         for(int i=1;i<=n;i++){33             int t;34             cin>>ap[apn].x>>ap[apn].y;apn++;35             cin>>ap[apn].x>>ap[apn].y;apn++;36             cin>>ap[apn].x>>ap[apn].y;apn++;37             cin>>t;38             ap[apn-3].cost=ap[apn-2].cost=ap[apn-1].cost=ap[apn].cost=t;39             if((ap[apn-1].x-ap[apn-2].x)*(ap[apn-1].x-ap[apn-3].x)+(ap[apn-1].y-ap[apn-2].y)*(ap[apn-1].y-ap[apn-3].y)==0)40                 ap[apn].x=0-ap[apn-1].x+ap[apn-2].x+ap[apn-3].x,ap[apn].y=0-ap[apn-1].y+ap[apn-2].y+ap[apn-3].y,apn++;41             else if((ap[apn-3].x-ap[apn-1].x)*(ap[apn-3].x-ap[apn-2].x)+(ap[apn-3].y-ap[apn-1].y)*(ap[apn-3].y-ap[apn-2].y)==0)42                 ap[apn].x=ap[apn-1].x+ap[apn-2].x-ap[apn-3].x,ap[apn].y=ap[apn-1].y+ap[apn-2].y-ap[apn-3].y,apn++;43             else44                 ap[apn].x=ap[apn-1].x-ap[apn-2].x+ap[apn-3].x,ap[apn].y=ap[apn-1].y-ap[apn-2].y+ap[apn-3].y,apn++;45         }46         47         for(int i=0;i<apn;i++)48             if(i/4!=sx)49                 for(int j=0;j<4;j++)50                     dis[i]=min(dis[i],dist(i,sx*4+j))*air;51         for(int i=0;i<4;i++)dis[sx*4+i]=0;52         53         queue<int> q;54         for(int i=0;i<4;i++)q.push(sx*4+i);55         56         while(!q.empty()){57             int x=q.front();q.pop();58             for(int i=0;i<apn;i++)59                     if(i/4==x/4){60                         if(dis[i]>dis[x]+dist(x,i)*ap[i].cost){61                             q.push(i);62                             dis[i]=dis[x]+dist(x,i)*ap[i].cost;63                         }64                     }65                     else66                         if(dis[i]>dis[x]+dist(x,i)*air){67                             q.push(i);68                             dis[i]=dis[x]+dist(x,i)*air;69                         }70         }71         72         for(int i=0;i<4;i++)res=min(res,dis[tx*4+i]);73         printf("%.2lf",(double)res/DIF);74     }75     return 0;76 }