CPP - Closest Pair Problem

no tags 

 

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