牛的旅行

题目描述

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

输入

第一行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

本地修订说明

明确全图分量最大直径目标、N≥2和六位精度；专门加入第三个大分量测试，避免只最小化被合并两块。

本地评测数据为独立构造和核验的教学训练数据，非官方原版数据。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：明确全图分量最大直径目标、N≥2和六位精度；专门加入第三个大分量测试，避免只最小化被合并两块。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1343。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。