1539 . 星際戰爭，由你阻止
TopCoder
Tags
Description
3145 A.D.，整個 γκμ- 23 星系群瀰漫在空前絕後的緊張氣氛中，
由於近期一次星際會議的不和，加深了彼此之間原本便不太友善的態度，
更要命的是，甚至在某些星系之間發生的衝突已經有可能發展成星際之間的大戰!!
注意，這不是星球跟星球間的戰爭，而是星系之間的大戰，一旦爆發那影響之大!!
因此，身為中央管理局--調和及處理眾星系之間事務的機構 之中管理階層的一份子，
你與你的團隊迫切的關注著這場暴風雨前的寧靜，
為了阻止這場可能發生的戰爭，你蒐集了所有最近發生的規模較小的衝突事件，
找出了幾個關係較危險的星系，他們之間的關係都不是很好，
現在，知道了個星系對於管理局的座標後，你想趕快找出哪兩個星系距離最近，畢竟距離越近發生衝突的可能性越大!
但由於星系的數量太多了，因此你需要寫一個程式以迅速的計算出結果。
對於上面這組 Case 來說: 座標 (-5,-14,0) 的星系與座標 (-7,-8,-1) 的星系直線距離最近，
且座標 (0,0,0) 為中央管理局的座標，絕對不會有其他星系的座標為 (0,0,0)。
Input Format
第一行有一個整數 N ($2\leq N\leq 5\times 10^ 5$)，代表此區域共有 N 個需要注意的星系。
之後的 N 行皆包含三個實數，分別表示一個星系對於中央管理局的 x, y, z 座標。($-2^ {32}\leq x,y,z\leq 2^ {32}$)
Output Format
請輸出一行警告給管理局的同仁，告訴他們最有可能發生衝突的兩個星系之編號分別為何，以及兩星系之間的距離。
警告格式如下：
WARNING: galaxyA and galaxyB in MIN_D Uu
（A,B為兩星系之編號，MIN_D為他們之間的直線距離。你輸出的距離只要和答案的相對誤差或絕對誤差$\leq 10^ {-6}$就會被視為正確。）
ps. Uu 即 Universe unit(宇宙單位)
對於這兩個星系請將編號較小的星系輸出在前面。
(你可以假設解答都是唯一的，不會有兩組以上距離都最短的情形在測試資料中出現。)
Sample Input 1
12 11 32
6 5 -4
-17 6 12
-1 -12 -7
-5 -14 0
-7 -8 -1
7 -2 5
Sample Output 1
Hints
( 原始圖片來源: Wikipedia Commons )
Problem Source
原TIOJ1539 / Problem Setter: Skyly
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |