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
cis_pie: 2020-08-18 17:37:05

Can be done using line sweep algorithm in nlogn

manish1101: 2020-06-13 11:02:06

I have submitted more than 15 times but still stuck at line 179 in my code https://ideone.com/DKZPzF
Please someone help

Saksham : 2020-04-03 21:30:21

'rounding to 6 digits' - this got me.

Eddy Cael: 2020-01-16 05:09:30

You can use long long or double, it no makes a real difference.

Eddy Cael: 2020-01-16 05:04:33

Don't waste time in precision issues... Make sure that the algorithm is right and a<b. That's all.

pyshubh95: 2019-11-10 19:35:02

time waste

playmaker02: 2019-07-05 11:22:00

acos

playmaker02: 2019-07-05 11:20:41

atan2(y,x)

eng_hardik: 2019-05-11 14:48:33

Getting TLE with n*logn algo in JAVA...Anyone got AC in JAVA ??

ameernsr: 2019-02-10 14:04:48

badihijat


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