TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

20.2% (26/129)

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

7
12 11 32
6 5 -4
-17 6 12
-1 -12 -7
-5 -14 0
-7 -8 -1
7 -2 5

Sample Output

WARNING: galaxy5 and galaxy6 in 6.403 Uu

Hints

( 原始圖片來源: Wikipedia Commons )

Problem Source

原TIOJ1539 / Problem Setter: Skyly

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1900 65536 262144
1 1900 65536 262144
2 1900 65536 262144
3 1900 65536 262144
4 1900 65536 262144
5 1900 65536 262144
6 1900 65536 262144
7 1900 65536 262144
8 1900 65536 262144
9 1900 65536 262144