某教授的普通物理課程,由於增加了程式模擬物理現象的作業,因此得到許多媒體的報導。
某天教授出了程式作業:用很多個小球模擬馬克士威-波茲曼分布。方法是這樣:在三維空間中模擬很多個小球,使它們不斷彈性碰撞,並繪製速度的分布圖。
然而,多數人做出來的程式都運作得非常緩慢,時常當機。有人猜測是因為使用python程式語言,又用了VPython繪圖的關係,但是平常的作業都不會發生這種事情。
經過仔細研究之後,總算發現了原因:判斷小球兩兩之間有沒有產生碰撞太花時間了。他也很快發現了解決方法:由於小球的運動十分隨機,不大可能有很多組小球同時碰撞的情況,因此每次只要找到距離最近的兩顆球,判斷它們有沒有碰撞就可以了。
但是很快地,大家也發現要找到距離最近的兩顆球並不是一件簡單的事情,尤其在python上實作更顯得困難。
為了簡化問題,你只要先求出距離最近的兩顆球球心之間的距離就可以了。
第一行有一個整數$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 |
輸出一個正整數$D$,代表距離最近的兩顆球球心之間的距離為$\sqrt{D}$。
傳說中,在普通物理的課堂中,流傳著這麼一張圖片,用以警惕同學們要慎選組員。
Problem set / Description by Yihda Yol
建國中學105學年度校內第四次模擬賽pC
No. | Testdata Range | Score |
---|---|---|
1 | 0~2 | 7 |
2 | 0~8 | 28 |
3 | 0~16 | 65 |