2791: 把儿的网吧

    把儿的网吧里呈星点式地分布有n台机子，某些机子间连接有网线，连有网线的两台机子可以直接互访。这些网线都是直线连接两端的机子。只要一台机子可以间接地通过中间的若干台机子访问到另一台机子，我们都说这两台机子互相连通。互相连通的两台机子可能有多条路线进行互访，为了使访问速度更快，机器会选择路线最短的一条。
    由于网线条数有限，这些机子并不全都连通。根据机子的连通性，把儿把这些机子分成了若干个“区”。在打网络游戏时，一个区的网速由这个区中互访时经过网线最长的两台机子决定，这个路线越长，整个区的网络游戏速度越慢。现在把儿搞到了一根新的网线，他希望能把其中的两个区连成一个区，并要使得这个新的区的网速最快。
    下图是把儿的网吧中的一个区的示意图。五台机子分别安放在坐标(10,10)、(15,10)、(20,10)、(15,15)、(20,15)上。这个区的网速由机子A和E决定，因为它们间互相访问的路线A-B-E是所有两机互访路线中最长的一条。这个长度大约等于12.07106。

          15,15   20,15
             D     E
             *----*
             |   /|
             |  / |
             | /  |
             |/   |
      *------*----*
      A      B     C
   10,10  15,10   20,10

    把儿的网吧中还有另一个区，示意图如下。

               *F 30,15
              /
             /
            /
           /
          *------*
          G      H
        25,10   30,10

    我们用一个对称的邻接矩阵表示哪些机子是直接相连的。对于上例中把儿的网吧，下表描述了机子的连接状态。

          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

    现在，把儿需要选两个区（这个例子中只有两个区）连成一个区，使这个新区里任意两台机子间的互访路线中最长的一条最短。

    从文件netbar.in中读入数据
    数据的第一行是一个数n，代表把儿的网吧中有n台机子。
    以下n行中每一行有两个用空格隔开的数X和Y。其中，第i行的两个数Xi和Yi表示第i个机子的坐标。这些坐标值是不超过100 000的非负整数。
    接下来输入文件将给出一个邻接矩阵，它描述了任两台机子间是否有网线直接连接。其中，1代表有网线直接连接，0代表没有网线直接连接。这个邻接矩阵的主对角线上的数都为0。
    我们的输入数据保证网吧将存在至少两个互不连通的区。

    输出一个小数到netbar.out中。这个小数应保留小数点后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