回分類題庫
h117: B.重建薑餅部落
關鍵字: NPSC 2013 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 33 Times / 25 Users | Submit : 161 Times / 41 Users | Accepted rate : 61%
題目加入時間 : 2013-12-17 13:36

Content: 简体中文

在飛行麵條怪物的襲擊之後,薑餅長老讓倖存的薑餅人們各自分散到北方大地上建立新的居住處。當每個薑餅人都安頓好之後,薑餅長老發現新的薑餅部落範圍比原本大多了,互相聯絡變得困難許多。

有鑑於此,薑餅長老打算在每個薑餅人聚集點架設通訊用基地台。為了架設方便,所有基地台都被設計成能提供以自身為中心半徑恰為R 的圓形通訊範圍。兩座基地台的通訊範圍只要有覆蓋或相接就可以相互聯絡,而距離較遠的基地台也可以如下圖般經由聯絡其他基地台取得聯繫。

薑餅長老已經統計好了需要架設基地台的位置,請你計算讓所有基地台都能相互聯絡所需要的最小整數 R 為何? 

Input:

輸入的第一行有一個正整數 T (T<=100),代表測試資料的組數。

每一組測試資料的第一行有一個正整數 N (2<=N<=1000) 代表基地台架設點的數量。下面 N 行每行有兩個整數 Xi, Yi 以空白隔開 (−109 <= Xi, Yi <= 109) 代表第 i 個架設點的平面座標。 

Output:

對於每一筆測試資料請輸出一行,包含一個整數表示 R。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
4
0 0
0 -1
0 1
100 0
4
0 0
0 5
0 100
0 105
2
-1000000000 1000000000
1000000000 -1000000000

Sample Output :

50
48
1414213563

Hint :

Author :

NPSC 2013 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum