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
shef:
2015-07-30 16:40:09
Did anyone identify what are we getting WA on 12th case even after using long long int |
|
TP:
2015-07-02 17:33:04
Getting WA did n't understand why this is happening ? Only after the 12th case it shows wrong answer? Last edit: 2015-07-02 21:37:44 |
|
Dewang Sultania:
2015-06-23 07:41:17
getting WA12 even after using long long int can any1 pls find the mistake
|
|
sHaShAnK sHeKhAr:
2015-06-22 07:41:25
Use long long int :) |
|
Rishab Banerjee:
2015-05-24 17:23:43
12th test case WA no idea why :-( I have used line-sweep algorithm Last edit: 2015-05-24 17:24:32 |
|
Kamil Debowski:
2015-03-16 16:54:01
guys, be careful about "Round c to 6 decimal digits." |
|
S Akira Sai Karthik:
2015-02-06 06:41:21
Getting wrong answer after test case 12 any idea ??? |
|
Chuyên Nhật CNN:
2014-08-23 18:00:52
I think the test cases are week :| |
|
Erdem Kirez:
2014-07-31 13:48:14
Be careful about output.
|
|
bat2009fifa:
2014-02-06 13:08:40
you can never trust double or even long double more than long long int.
|
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 |