CLOPPAIR - Closest Point Pair


You are given N points on a plane and your task is to find a pair of points with the smallest euclidean distance between them.

All points will be unique and there is only one pair with the smallest distance.

Input

First line of input will contain N (2<=N<=50000) and then N lines follow each line contains two integers giving the X and Y coordinate of the point. Absolute value of X,Y will be atmost 10^6.

Output

Output 3 numbers a b c, where a,b (a<b) are the indexes (0 based) of the point pair in the input and c is the distance between them. Round c to 6 decimal digits.

See samples for more clarification.

 

Input: 
5
0 0
0 1
100 45
2 3
9 9

Output:

0 1 1.000000
Input: 
5
0 0
-4 1
-7 -2
4 5
1 1

Output:

0 4 1.414214

hide comments
Rishab Banerjee: 2015-05-24 17:23:43

12th test case WA no idea why :-( I have used line-sweep algorithm

Last edit: 2015-05-24 17:24:32
Kamil Debowski: 2015-03-16 16:54:01

guys, be careful about "Round c to 6 decimal digits."

S Akira Sai Karthik: 2015-02-06 06:41:21

Getting wrong answer after test case 12 any idea ???

Chuyên Nhật CNN: 2014-08-23 18:00:52

I think the test cases are week :|

Erdem Kirez: 2014-07-31 13:48:14

Be careful about output.
"(a<b)".

bat2009fifa: 2014-02-06 13:08:40

you can never trust double or even long double more than long long int.
i got ac by paying attention to this trick.

innovolt: 2013-11-09 18:56:51

any spcl test case...getting WA after 12th test case

Ashutosh Singla: 2013-08-25 18:34:14

take care of limits

Last edit: 2013-08-26 21:22:42
i_hate_myself: 2013-02-22 19:15:11

getting wrng ans on 12th test case...give me some more test case.. ???

Monkey D. Luffy : 2013-02-15 22:09:13

pheww it got up to 12th test case then wa...


Added by:SALVO
Date:2011-04-14
Time limit:0.169s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Standard Problem