TopCoder

User's AC Ratio

97.6% (41/42)

Submission's AC Ratio

42.3% (69/163)

Description

身為一個喜歡玩電視遊樂器的人,大明老早就存好錢,在PS3出的那一天就搶購了一台回來。但問題來了,大明的媽媽規定他期末考前不能玩PS3,身為大明的好友,為了讓大明可以偷偷的玩 PS3,也為了讓以後去大明家的時候可以玩PS3,你決定助他一臂之力。

經過探查以後發現,大明的媽媽在看電視的時候喜歡吃一種特別的零食,所以大明只要在某台電視旁邊放這種零食,就可以保證他媽媽會去那看電視,大明就可以趁機用另一台電視玩 PS3 了!為了降低被抓到偷打電玩的機率,大明會在他媽媽看電視的時候到最遠的那台電視去玩 PS3。大明已經量好家裡的每一台電視的座標 (X, Y)。請你好人做到底,幫忙找出要在哪裡放零食、在哪裡偷玩最不容易被發現。

Input Format

輸入檔中有許多組輸入,每組輸入的第一行是大明家的電視機數量 N(2 ≦ N ≦ 3000),之後的 N行每行有兩個數字,分別代表第 0 到第 N-1 台電視機的X、Y座標(0 ≦ X, Y ≦ 10000)。N = 0 為檔案結束,不須處理這組輸入。

Output Format

對每組輸入請輸出兩個數字 a、b(a < b),分別代表放零食的電視機和要用來偷玩的電視機編號。如果有很多組解,輸出a最小的那個。若還是有多組解,輸出b最小的那個。

Sample Input

4
0 0
1 0
0 1
1 1
0

Sample Output

0 3

Hints

Problem Source

原TIOJ1105 / NPSC2006決賽(prob H)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144