描述 Description
农民 John 的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧场通过任何路径都不连通。这样，Farmer John 就有多个牧场了。
John 想在牧场里添加一条路径(注意，恰好一条)。对这条路径有以下限制：
一个牧场的直径就是牧场中最远的两个牧区的距离 (本题中所提到的所有距离指的都是最短的距离)。考虑如下的有 5 个牧区的牧场，牧区用“*” 表示，路径用直线表示。每一个牧区都有自己的坐标：
(15,15) (20,15)
D E
——-
| _/|
| _/ |
| _/ |
|/ |
——-——-*
A B C
(10,10) (15,10) (20,10)
这个牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E，它们之间的最短路径是 A-B-E。
这里是另一个牧场：
*F(30,15)
_/
_/
_/
/
——-
G H
(25,10) (30,10)
添加 C 至 G 一条路径后便是：
(15,15) (20,15) (30,15)
D E F
——- *
| /| /
| / | /
| / | /
|/ | /
——-——-——-——-*
A B C G H
(10,10) (15,10) (20,10) (25,10) (30,10)
整个牧场直径约为 22.071068。 在目前的情景中，他刚好有两个牧场。John 将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。
注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。
输入文件包括牧区、它们各自的坐标，还有一个如下的对称邻接矩阵：
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
其他邻接表中可能直接使用行列而不使用字母来表示每一个牧区。输入数据中不包括牧区的名字。
输入文件至少包括两个不连通的牧区。
请编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。输出在所有牧场中最小的可能的直径。
描述的对称邻接矩阵。
输出格式 OutputFormat
只有一行，包括一个实数，表示所求直径。数字保留六位小数。
只需要打到小数点后六位即可，不要做任何特别的四舍五入处理。
样例输入 SampleInput
30
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
0 100
1 100
2 100
3 100
4 100
5 100
6 100
7 100
8 100
9 100
10 100
11 100
12 100
13 100
14 100
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
111111111111111000000000000000
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
000000000000000111111111111111
样例输出 SampleOutput
114.000000
代码 Code
Floyd 求出任意两个牧区的距离，然后每次选择两个不在同一个牧场的牧区连通，比较最小直径。最后保证原牧场的直径不大于答案值。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
#define inf 0x7fffffff/11
struct point
{
int z,y,x;
};
point p[100001];
double a[151][151];
double maxdis[151];
int i,j,t,n,m,l,r,k,s;
double ans;
char c[151];
double dis(point a,point b)
{
double c,d;
c=a.x-b.x;d=a.y-b.y;
return sqrt((double)c*c+(double)d*d);
}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d%d\n",&p[i].x,&p[i].y);
for (i=1;i<=n;i++)
{
scanf("%s",&c);
for (j=0;j<strlen(c);j++)
{
a[i][j+1]=(c[j]=='0')?inf:dis(p[i],p[j+1]);
if (i==j+1) a[i][j+1]=0;
}
}
for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++)
{
a[i][j]=fmin(a[i][j],a[i][k]+a[k][j]);
}
for (i=1;i<=n;i++) for (j=1;j<=n;j++)
{
if (a[i][j]>maxdis[i] && a[i][j]!=inf) maxdis[i]=a[i][j];
}
ans=inf;
for (i=1;i<=n;i++) for (j=1;j<=n;j++)
{
if (a[i][j]==inf)
{
ans=fmin(ans,dis(p[i],p[j])+maxdis[i]+maxdis[j]);
}
}
for (i=1;i<=n;i++) ans=fmax(ans,maxdis[i]);
printf("%.6lf\n",ans);
return 0;
}