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
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

tommydong: 2018-12-15 04:27:01

I got WA on test 12. It was not just a presentation error. I was totally wrong. Perhaps the test before 12 is weak.

yaseenmollik: 2018-11-30 10:36:50

AC in 5 go -_-

No need to use long long int instead of double...just make sure that a < b and your algorithm is correct..

edit: You must also use "cout << fixed << setprecision(6);" before printing the answer...otherwise it will give WA

Last edit: 2018-11-30 10:39:11
pkhrag: 2018-09-19 11:25:41

Getting TLE with n*logn algo in C++. Can anyone help?


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