牛的旅行

题目描述

给定至少两个连通分量的无向牧场图，边长为坐标直线距离。必须添加一条连接不同分量的边，求添加后所有连通分量直径最大值的最小值。没有合并的分量也计入最终目标；线段交叉不产生新结点。

输入

第一行N，2≤N≤150；随后N行互异整数坐标，0≤X,Y≤100000；再N行01邻接矩阵，对称且对角为0。保证至少两个连通分量。

输出

输出非负长度，保留六位小数。以精确最优值四舍五入到六位后的数值为基准，允许绝对误差≤10^-6，采用数值特判。

输入样例

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