34. 交通工具

0 Judge

Code: 0


平面最遠點對

交通工具

題目敘述

海牛最近想買車,可是海牛國很大,而且有很多城市,他怕車子開到一半可能會沒油,所以他希望可以買足夠油量的車,讓他可以從任兩個城市間移動而不會沒油。海牛國的城市分布在一個平面有自己的座標,海牛給你所有城市的座標,希望你幫他找出海牛國間距離最遠的兩個城市的距離,讓他可以知道要買多少油量的車。

為了避免浮點數誤差,請告訴他最遠兩個城市的距離的平方。

輸入說明

第一行有一個$T(T \leq 10)$,代表測資數。 接下來每筆測資,第一行有一個N,代表城市數, 第二行有$2 \cdot N$個數字$x_1, y_1, ..., x_N, y_N$,代表N個城市的座標,$-10^9 \leq x, y \leq 10^9$。

輸出說明

對於每筆測資,輸出一行最遠距離的平方。

範例輸入

範例輸出

子題一[30%]

$2 \leq N \leq 100$

子題二[30%]

$2 \leq N \leq 10000$

子題三[40%]

$2 \leq N \leq 100000$


Judge Setting

run-time limit: 1000 ms
memory limit: 104857600 byte
測資數量: 3