TopCoder

User's AC Ratio

57.1% (8/14)

Submission's AC Ratio

34.2% (110/322)

Description

某教授的普通物理課程,由於增加了程式模擬物理現象的作業,因此得到許多媒體的報導

某天教授出了程式作業:用很多個小球模擬馬克士威-波茲曼分布。方法是這樣:在三維空間中模擬很多個小球,使它們不斷彈性碰撞,並繪製速度的分布圖。
然而,多數人做出來的程式都運作得非常緩慢,時常當機。有人猜測是因為使用python程式語言,又用了VPython繪圖的關係,但是平常的作業都不會發生這種事情。

經過仔細研究之後,總算發現了原因:判斷小球兩兩之間有沒有產生碰撞太花時間了。他也很快發現了解決方法:由於小球的運動十分隨機,不大可能有很多組小球同時碰撞的情況,因此每次只要找到距離最近的兩顆球,判斷它們有沒有碰撞就可以了。
但是很快地,大家也發現要找到距離最近的兩顆球並不是一件簡單的事情,尤其在python上實作更顯得困難。
為了簡化問題,你只要先求出距離最近的兩顆球球心之間的距離就可以了。

Input Format

第一行有一個整數$N$,代表小球數量。
接下來$N$行,每行有三個整數$X_i, Y_i, Z_i$,代表第$i$個小球的X、Y、Z座標值。保證所有小球的位置都相異。
對於所有的測資,$N\leq 10^ 5; |X_i|, |Y_i|, |Z_i| \leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0~2) $N\leq 100, |X_i|, |Y_i|, |Z_i| \leq 10^ 4$ 7
2 (0~8) $N\leq 10^ 4$ 28
3 (0~16) 無限制 65

Output Format

輸出一個正整數$D$,代表距離最近的兩顆球球心之間的距離為$\sqrt{D}$。

Sample Input

5
1 1 1
3 3 3
4 8 6
2 9 1
4 5 1

Sample Output

9

Hints

傳說中,在普通物理的課堂中,流傳著這麼一張圖片,用以警惕同學們要慎選組員。

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校內第四次模擬賽pC

Subtasks

For Testdata: 0 ~ 2, Score: 7
For Testdata: 0 ~ 8, Score: 28
For Testdata: 0 ~ 16, Score: 65
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 512
1 1000 131072 512
2 1000 131072 512
3 1000 131072 512
4 1000 131072 512
5 1000 131072 512
6 1000 131072 512
7 1000 131072 512
8 400 131072 512
9 400 131072 512
10 400 131072 512
11 400 131072 512
12 400 131072 512
13 400 131072 512
14 400 131072 512
15 400 131072 512
16 400 131072 512