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 at most 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
beast007: 2024-11-07 13:18:01

it can be done using line sweep, I did.

Last edit: 2024-11-07 13:18:32
mahan07: 2024-08-15 14:40:52

easy problem

bigbardia: 2024-08-15 14:40:10

AC in one GO!
Mo's algorithm + Bitmasking

king_87arshia: 2024-08-15 14:38:39

AC in one go using MO s Algorithm(Modified Operations Algorithm)

pb2008: 2024-08-15 14:32:56

EZ, AC IN ONE GO
just use static programming and ternary lifting

atomic_lattice: 2023-05-22 10:01:12

REMEMBER a < b and EXACTLY 6 digits

mreza5760: 2022-10-28 11:31:26

3 important thing
1. find the answer in long long then get the sqrt
2. be careful about a < b
3. use 1ll* in some part of code

ppap_1264589: 2021-09-12 17:33:47

Make sure your output is (a < b)
Make sure that you use cout << fixed << setprecision(6) before printing answer
Finally, make sure your algorithm is correct then you would get accepted

princemishra: 2021-06-05 14:53:36

even n(logn)^2 worked

shashwat28: 2021-01-02 13:23:43

Those who are stuck on TC 12 ,it wants exactly 6 digits after decimal no more no less :)


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