CPP - Closest Pair Problem
Given n points on the plane, each represented by (x, y) coordinates, find a pair of points with
the smallest distance between them.
Given n points on the plane, each represented by (x, y) coordinates, find a pair of points with the smallest distance between them.
Input
The first line of input will contain the number of points, n (2 <= n <= 30,000). Each of the next n lines will contain two integers x and y (-1,000,000 <= x, y <= 1,000,000). The ith line contains the coordinates for the ith point.
Output
Print to the ouput a single floating point number d, denoting the distance between the closest pair of points. d should contain exactly 6 digits after the decimal.
Example
Input:
5
0 0
-4 1
-7 -2
4 5
1 1
Output:
1.414214
hide comments
markhaml:
2019-03-08 19:09:22
I am assuming 100 score means the solution was correct? |
|
yaseenmollik:
2018-11-30 11:48:37
100 Score using divide and conquer :D |
|
sultania23:
2017-07-19 16:07:37
score is on which basis?? |
|
ihak:
2015-07-28 21:06:44
Sweep Line Algorithm :) |
|
sw40:
2014-03-29 08:47:54
Weak tests |
|
NISHANT RAJ:
2013-12-09 19:23:13
jst use simple sorting...
|
Added by: | Atef |
Date: | 2011-10-16 |
Time limit: | 0.400s-0.600s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Standard problem |