| 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
|
|||||||||
|
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. |
|||||||||
|
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 |
|||||||||
|
2018-09-19 11:25:41
Getting TLE with n*logn algo in C++. Can anyone help? |
|||||||||
|
2018-08-25 10:43:10
What the hell if wrong with that test 12, what do you mean to use long long int?? |
|||||||||
|
2018-04-25 07:54:38
This problem isn't suitable for python. An n*logn divide and conquer algorithm will pass in c++ but get a TLE in python. For the people getting WA in test case 11/12, it's the precision of the output ( you should use << fixed << setprecision(6)<< ). It might also be a problem in the order of the two outputs a and b so make sure a < b. |
|||||||||
|
2017-10-04 13:05:27
For test case 12 use std::fixed; before using std::setprecision(6); |
|||||||||
|
2017-08-20 03:46:02
12th case solved by checking my minimum (default) distance. |
|||||||||
|
2017-08-19 18:01:53
also this problem was never pass with python. The time limit set is too little! |
|||||||||
|
2017-08-19 17:52:06
I used double instead of long long int and still passed (?_?) |
|||||||||
|
2017-08-19 17:29:35
omg guys. I managed to get past test case 12. So what happened was that my solution was correct, but because I used cout with setprecision(7), it displayed the wrong answer for some reason. So if you want to pass this challenge, use printf update: lol I realized I need to use fixed with setprecision to get it to the right decimal places. cout << setprecision(6) << fixed << distance; Last edit: 2017-08-19 17:34:00 |
|||||||||
RSS