TopCoder

smgshabc123

User's AC Ratio

100.0% (2/2)

100.0% (2/2)

在疫情嚴重之際，小風城研擬了一個封城規定。每個人只能在以住處為圓心，半徑 $R$ 的圓內活動。在允許的活動範圍內，活動區域有相交的兩個居民可以互相傳遞物品，活動區域只相交於一點也可以。

如果有兩個居民無法通過一系列傳遞互相來往，那他們生活會很不方便。小風想知道最小的整數 $R$，使得在這樣的封城狀態下，任兩位居民還是能通過一系列傳遞來往。

輸入包含多筆測資。輸入的第一行是一個整數 $T$ 代表測資筆數。
每一筆測試資料第一行是一個整數 $N$，代表小風城一共有幾個居民。接下來的 $N$ 行是兩個以空白分隔的正整數，分別代表該居民所在位置的 $x,y$ 座標。

對於所有測資，保證 $T\le 100$，$2\le N\le 1000$，$-10^ 9\le x,y\le 10^ 9$。
測資額外保證單筆輸入 $N$ 的總和不超過 $2000$。注意到可能有兩個居民在同一個位置。

每筆測資輸出一行一個整數，代表最小的封城半徑 $R$。

3
4
0 0
0 -1
0 1
100 0
4
0 0
0 5
0 100
0 105
2
-1000000000 1000000000
1000000000 -1000000000

50
48
1414213563

NPSC 2013 高中組初賽

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	0~17	無額外限制	100

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2
16	1000	524288	65536	2
17	1000	524288	65536	2