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!
|
|
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
|
|
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
|
|
ppap_1264589:
2021-09-12 17:33:47
Make sure your output is (a < b)
|
|
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 |