題目 1336:
牛的旅行
時間限制: 2s
內(nèi)存限制: 320MB 提交: 55 解決: 35
題目描述
農(nóng)民John的農(nóng)場里有很多牧區(qū)。有的路徑連接一些特定的牧區(qū)。一片所有連通的牧區(qū)稱為一個牧場。但是就目前而言，你能看到至少有兩個牧區(qū)不連通?，F(xiàn)在，John想在農(nóng)場里添加一條路徑 ( 注意，恰好一條 )。對這條路徑有這樣的限制：一個牧場的直徑就是牧場中最遠(yuǎn)的兩個牧區(qū)的距離(本題中所提到的所有距離指的都是最短的距離)?？紤]如下的兩個牧場，圖１是有5個牧區(qū)的牧場，牧區(qū)用“*”表示，路徑用直線表示。每一個牧區(qū)都有自己的坐標(biāo)：
圖１所示的牧場的直徑大約是12.07106, 最遠(yuǎn)的兩個牧區(qū)是 A 和 E，它們之間的最短路徑是 A-B-E。
這兩個牧場都在John的農(nóng)場上。John將會在兩個牧場中各選一個牧區(qū)，然后用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。注意，如果兩條路徑中途相交，我們不認(rèn)為它們是連通的。只有兩條路徑在同一個牧區(qū)相交，我們才認(rèn)為它們是連通的。現(xiàn)在請你編程找出一條連接兩個不同牧場的路徑，使得連上這條路徑后，這個更大的新牧場有最小的直徑。
輸入格式
第1行: 一個整數(shù)N (1 < = N < = 150), 表示牧區(qū)數(shù) 第2到N+1行: 每行兩個整數(shù)X,Y (0 < = X ,Y< = 100000), 表示N個牧區(qū)的坐標(biāo)。注意每個 牧區(qū)的坐標(biāo)都是不一樣的。
第N+2行到第2*N+1行: 每行包括N個數(shù)字(0或1) 表示如上文描述的對稱鄰接矩陣。
例如，題目描述中的兩個牧場的矩陣描述如下：
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
輸入數(shù)據(jù)中至少包括兩個不連通的牧區(qū)。
輸出格式
只有一行，包括一個實數(shù)，表示所求直徑。數(shù)字保留六位小數(shù)。
樣例輸入
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