農民John的農場裡有很多牧區。有的路徑連接一些特定的牧區。一片所有連通的牧區稱為一個牧場。但是就目前而言，你能看到至少有兩個牧區通過任何路徑都不連通。這樣，農民John就有多個牧場了。
John想在農場裡添加一條路徑(注意，恰好一條)。對這條路徑有以下限制：
一個牧場的直徑就是牧場中最遠的兩個牧區的距離(本題中所提到的所有距離指的都是最短的距離)。考慮如下的有5個牧區的牧場，牧區用“*”表示，路徑用直線表示。每一個牧區都有自己的坐標：
15,15 20,15
D E
*-------*
| _/|
| _/ |
| _/ |
|/ |
*--------*-------*
A B C
10,10 15,10 20,10
這個牧場的直徑大約是12.07106, 最遠的兩個牧區是A和E，它們之間的最短路徑是A-B-E。
這裡是另一個牧場：
*F 30,15
/
_/
_/
/
*------*
G H
25,10 30,10
這兩個牧場都在John的農場上。John將會在兩個牧場中各選一個牧區，然後用一條路徑連起來，使得連通後這個新的更大的牧場有最小的直徑。
注意，如果兩條路徑中途相交，我們不認為它們是連通的。只有兩條路徑在同一個牧區相交，我們才認為它們是連通的。
輸入文件包括牧區、它們各自的坐標，還有一個如下的對稱鄰接矩陣：
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
輸入文件至少包括兩個不連通的牧區。
請編程找出一條連接兩個不同牧場的路徑，使得連上這條路徑後，這個更大的新牧場有最小的直徑。
第1行: 一個整數N (1 <= N <= 150), 表示牧區數
第2到N+1行: 每行兩個整數X,Y (0 <= X ,Y<= 100000), 表示N個牧區的坐標。注意每個 牧區的坐標都是不一樣的。
第N+2行到第2*N+1行: 每行包括N個數字(0或1) 表示如上文描述的對稱鄰接矩陣。
只有一行，包括一個實數，表示所求直徑。數字保留六位小數。
樣例輸入 Sample Input8
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
數據范圍及提示 Data Size & Hint1s
scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 sscanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格canf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格 scanf會讀空格
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<cmath>
6 using namespace std;
7 double maxn=1e12;
8 double x[1001];
9 double y[1001];
10 double cd(int i,int j)
11 {
12 return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
13 }
14 double map[1001][1001];
15 double m[10001];//點i可以到達的最大距離
16 int main()
17 {
18 int n;
19 scanf("%d",&n);
20 for(int i=1;i<=n;i++)
21 {
22 scanf("%lf%lf",&x[i],&y[i]);
23 }
24 for(int i=1;i<=n;i++)
25 {
26 for(int j=1;j<=n;j++)
27 {
28 char kk;
29 //scanf("%c",&kk);
30 cin>>kk;
31 if(kk=='1')
32 {
33 double tmp=cd(i,j);
34 map[i][j]=tmp;
35 }
36 else
37 {
38 map[i][j]=maxn;
39 }
40 }
41 }
42 for(int k=1;k<=n;k++)
43 {
44 for(int i=1;i<=n;i++)
45 {
46 for(int j=1;j<=n;j++)
47 {
48 if(i!=j&&i!=k&&j!=k)
49 {
50 if(map[i][k]<maxn-1&&map[k][j]<maxn-1)
51 {
52 if(map[i][j]>map[i][k]+map[k][j])
53 {
54 map[i][j]=map[i][k]+map[k][j];
55 }
56 }
57
58 }
59
60 }
61 }
62 }
63 memset(m,0,sizeof(m));
64 for(int i=1;i<=n;i++)
65 {
66 for(int j=1;j<=n;j++)
67 {
68 if(map[i][j]<maxn-1)
69 {
70 if(m[i]<map[i][j])
71 {
72 m[i]=map[i][j];
73 }
74 }
75
76 }
77 }
78 double r2=maxn;
79 for(int i=1;i<=n;i++)
80 {
81 for(int j=1;j<=n;j++)
82 {
83 if(map[i][j]>maxn-1&&i!=j)
84 {
85 double tmp=cd(i,j);
86 double nn=m[i]+m[j]+tmp;
87 if(r2>nn)
88 r2=nn;
89 }
90 }
91 }
92 double r1=-1;
93 for(int i=1;i<=n;i++)
94 {
95
96 if(m[i]>r1)
97 r1=m[i];
98 }
99 printf("%.6lf",max(r1,r2));
100 return 0;
101 }
