题目描述
每个牧区有一个平面坐标,已有道路连接部分牧区;道路长度等于两端坐标的欧氏距离,双向通行。每个连通分量称为一个牧场,其直径是分量内任意两点最短距离的最大值。至少有两个牧场,现在恰好添加一条连接不同牧场的道路,使添加后全农场各连通牧场直径的最大值最小;原有的其他牧场直径也必须计入。道路在中途相交不产生连接。
样例牧区坐标| 结点 | x | y |
| A | 10 | 10 |
| B | 15 | 10 |
| C | 20 | 10 |
| D | 15 | 15 |
| E | 20 | 15 |
| F | 30 | 15 |
| G | 25 | 10 |
| H | 30 | 10 |
样例已有道路为 A-B、B-C、B-D、B-E、C-E、D-E、F-G、G-H。第一片牧场直径为 A-B-E 的 12.071068;新增 C-G 后全农场最大直径为 22.071068。
输入格式
第 1 行:一个整数N (2 ≤ N ≤ 150), 表示牧区数;
第 2 到 N+1 行:每行两个整数X,Y ( 0 ≤ X,Y≤ 100000 ), 表示N个牧区的坐标。每个牧区的坐标都是不一样的。
第 N+2 行到第 2*N+1 行:每行包括N个数字 ( 0或1 ) 表示一个对称邻接矩阵;每行是一个不含空格的 N 位01串,对角线为0。
例如,题目描述中的两个牧场的矩阵描述如下:
样例邻接矩阵 | 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 |
输入数据中至少包括两个不连通的牧区。
输出格式
只有一行,包括一个实数,表示所求答案。数字保留六位小数。允许绝对误差1e-6或相对误差1e-9,不得输出额外内容。
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
22.071068
来源
一本通在线评测 ybtbas-1343