Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
||||||||
2013-11-09 18:56:51 innovolt
any spcl test case...getting WA after 12th test case |
||||||||
2013-08-25 18:34:14 Ashutosh Singla
take care of limits Last edit: 2013-08-26 21:22:42 |
||||||||
2013-02-22 19:15:11 i_hate_myself
getting wrng ans on 12th test case...give me some more test case.. ??? |
||||||||
2013-02-15 22:09:13 Monkey D. Luffy
pheww it got up to 12th test case then wa... |
||||||||
2013-02-06 13:02:27 Utkarsh Shahdeo
Last edit: 2013-05-29 05:43:06 |
||||||||
2012-11-15 03:16:51 Ben Dean
There is not even one correct python submission. Is the time limit too low? |
||||||||
2012-05-18 17:50:39 !(NULL)
CLOSEST is a similar and more challenging problem. |
||||||||
2012-03-26 17:55:17 ramz
can you increase the time limit for Ruby. 1s is too less for an input of 50000 entries. |
||||||||
2011-05-28 04:20:25 SALVO
You can easily write an O(N^2) brute force solution and check for yourself. |
||||||||
2011-05-28 00:08:24 Krzysztof Lewko
Could i receive some tricky test case, SALVO ?:) |