1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<cmath>

 5 #include<iostream>

 6 using namespace std;

 7

 8 const int N=210;

 9 const double INF=300010.0;

10 double d[N][N];

11 struct node{int x,y;}a[N];

12

13 double mmin(double x,double y) {return x<y?x:y;}

14 double mmax(double x,double y) {return x>y?x:y;}

15 double dist(int i,int j) {return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));}

16 int main()

17 {

18     int n,T=0;

19     while (scanf("%d",&n)!=EOF && n)

20     {

21       int i,j,k;

22       for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);

23       for (i=1;i<=n;i++)

24        for (j=i;j<=n;j++)

25         d[i][j]=d[j][i]=dist(i,j);

26       for (k=1;k<=n;k++)//???

27        for (i=1;i<=n;i++)

28         for (j=1;j<=n;j++)//?i?j????1~k????????????

29           d[i][j]=mmin(d[i][j],mmax(d[i][k],d[k][j]));

30       printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++T,d[1][2]);

31     }

32 }

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<cmath>

 5 #include<algorithm>

 6 #include<iostream>

 7 using namespace std;

 8

 9 const int N=210,M=20010;

10 const double INF=300010.0;

11 int n,m;

12 int fa[N];

13 struct node{int x,y;}a[N];

14 struct edge

15 {

16     int x,y;

17     double d;

18     edge() {}

19     edge(int i,int j,double k) {x=i;y=j;d=k;}

20 }e[M];

21

22 double mmin(double x,double y) {return x<y?x:y;}

23 double mmax(double x,double y) {return x>y?x:y;}

24 bool cmp(edge x,edge y) {return x.d<y.d;}

25 double dist(int i,int j) {return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));}

26

27 int ffind(int x)

28 {

29     if (fa[x]!=x) fa[x]=ffind(fa[x]);

30     return fa[x];

31 }

32 double Kruskal(int u,int v)

33 {

34     int i;

35     for (i=1;i<=n;i++) fa[i]=i;

36     sort(e+1,e+1+m,cmp);

37     for (i=1;i<=m;i++)

38     {

39       int x=e[i].x,y=e[i].y;

40       int xx=ffind(x),yy=ffind(y);

41       if (xx!=yy)

42       {

43         fa[xx]=yy;

44         //if (x==u||y==u||x==v||y==v)//wrong

45           if (ffind(u)==ffind(v)) return e[i].d;

46       }

47     }

48 }

49 int main()

50 {

51     int T=0;

52     while (scanf("%d",&n)!=EOF && n)

53     {

54       int i,j;

55       for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);

56       m=0;

57       for (i=1;i<=n;i++)

58        for (j=i+1;j<=n;j++)

59         e[++m]=edge(i,j,dist(i,j));

60       printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++T,Kruskal(1,2));

61     }

62 }