TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

92.1% (117/127)

Submission's AC Ratio

38.4% (236/614)

Tags

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 1

4
0 0
1 0
0 1
1 1
0

Sample Output 1

0 3

Hints

Problem Source

原TIOJ1105 / NPSC2006決賽(prob H)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1