UOJ Logo FLYIOI UOJ

FLYIOI

#12. 把儿的网吧

问题描述

把儿的网吧里呈星点式地分布有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

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

输入数据

数据的第一行是一个数n,代表把儿的网吧中有n台机子。
以下n行中每一行有两个用空格隔开的数X和Y。其中,第i行的两个数Xi和Yi表示第i个机子的坐标。这些

坐标值是不超过100 000的非负整数。
接下来输入文件将给出一个邻接矩阵,它描述了任两台机子间是否有网线直接连接。其中,1代表有网线

直接连接,0代表没有网线直接连接。这个邻接矩阵的主对角线上的数都为0。
我们的输入数据保证网吧将存在至少两个互不连通的区。

输出数据

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

时间限制

各测试点1秒

内存限制

你的程序将被分配128MB的运行空间

数据规模

对于40%的数据,N<=10;
对于100%的数据,N<=150。