1 /* *********************************************** 2 Author        :SunYuefeng 3 Created Time  :2016/10/22 14:18:06 4 File Name     :A.cpp 5 ************************************************ */ 6  7 #include<cstdio> 8 #include<iostream> 9 #include<algorithm>10 #include<cmath>11 #include<cstring>12 #include<string>13 #include<bitset>14 #include<map>15 #include<set>16 #include<stack>17 #include<vector>18 #include<queue>19 #include<list>20 #define M(a,b) memset(a,b,sizeof(a))21 using namespace std;22 typedef long long ll;23 const int inf=0x3f3f3f3f;24 const int maxn=2e2+10;25 const int mod=1e7+7;26 int dx[8]= {0,0,1,-1,1,-1,1,-1};27 int dy[8]= {1,-1,0,0,-1,1,1,-1};28 29 int n,m;30 double way[maxn][maxn];31 double dis[maxn];32 bool vis[maxn];33 34 struct point{35     int x,y;36     double dist(point a){37         return sqrt((x-a.x)*(x-a.x)+(y-a.y)*(y-a.y));38     }39 }pt[maxn];40 41 void dijkstra(int x){42     for(int i=0;i<n;i++){43         dis[i]=way[0][i];44         vis[i]=false;45     }46     dis[x]=0;47     for(int i=0;i<n;i++){48         int k=-1;49         double min=inf;50         for(int j=0;j<n;j++){51             if(!vis[j]&&dis[j]<min){52                 min=dis[j];53                 k=j;54             }55         }56         if(k==1) break;57         vis[k]=true;58         for(int j=0;j<n;j++){59             if(!vis[j]&&dis[j]>max(dis[k],way[j][k])){60                 dis[j]=max(dis[k],way[j][k]);61             }62         }63     }64     printf("Frog Distance = %.3f\n\n",dis[1]);65 }66 67 int main()68 {69     //freopen("in.txt","r",stdin);70     //freopen("out.txt","w",stdout);71     int _case=1;72     while(~scanf("%d",&n)&&n){73         printf("Scenario #%d\n",_case++);74         for(int i=0;i<n;i++)75             for(int j=0;j<n;j++)76                 way[i][j]=inf;77         for(int i=0;i<n;i++)78             scanf("%d%d",&pt[i].x,&pt[i].y);79         for(int i=0;i<n;i++){80             for(int j=0;j<n;j++){81                 if(i==j) continue;82                 way[i][j]=pt[i].dist(pt[j]);83                 way[j][i]=pt[i].dist(pt[j]);84             }85         }86         dijkstra(0);87     }88     return 0;89 }