762 . 小風城
TopCoder
Tags
Description
在疫情嚴重之際，小風城研擬了一個封城規定。每個人只能在以住處為圓心，半徑 $R$ 的圓內活動。在允許的活動範圍內，活動區域有相交的兩個居民可以互相傳遞物品，活動區域只相交於一點也可以。
如果有兩個居民無法通過一系列傳遞互相來往，那他們生活會很不方便。小風想知道最小的整數 $R$，使得在這樣的封城狀態下，任兩位居民還是能通過一系列傳遞來往。
Input Format
輸入包含多筆測資。輸入的第一行是一個整數 $T$ 代表測資筆數。
每一筆測試資料第一行是一個整數 $N$，代表小風城一共有幾個居民。接下來的 $N$ 行是兩個以空白分隔的正整數，分別代表該居民所在位置的 $x,y$ 座標。
對於所有測資，保證 $T\le 100$，$2\le N\le 1000$，$-10^ 9\le x,y\le 10^ 9$。
測資額外保證單筆輸入 $N$ 的總和不超過 $2000$。注意到可能有兩個居民在同一個位置。
Output Format
每筆測資輸出一行一個整數，代表最小的封城半徑 $R$。
Sample Input 1
3
4
0 0
0 -1
0 1
100 0
4
0 0
0 5
0 100
0 105
2
-1000000000 1000000000
1000000000 -1000000000
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 1
50
48
1414213563
48
1414213563
Hints
Problem Source
NPSC 2013 高中組初賽
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~17 | 無額外限制 | 100 |