TopCoder

User's AC Ratio

57.1% (8/14)

Submission's AC Ratio

34.3% (98/286)

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)
0 1000 131072
1 1000 131072
2 1000 131072
3 1000 131072
4 1000 131072
5 1000 131072
6 1000 131072
7 1000 131072
8 400 131072
9 400 131072
10 400 131072
11 400 131072
12 400 131072
13 400 131072
14 400 131072
15 400 131072
16 400 131072