TopCoder

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

User's AC Ratio

68.8% (11/16)

Submission's AC Ratio

16.0% (38/238)

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

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

Sample Output 1

WARNING: galaxy5 and galaxy6 in 6.403 Uu

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1900 65536 262144 1
1 1900 65536 262144 2
2 1900 65536 262144 3
3 1900 65536 262144 4
4 1900 65536 262144 5
5 1900 65536 262144 6
6 1900 65536 262144 7
7 1900 65536 262144 8
8 1900 65536 262144 9
9 1900 65536 262144 10