Closest Pair

Limits 1s, 512 MB

You will be given NN pair of coordinates on a 2D space. You will determine distance between the closest pair of points.

The distance between any two points is calculated as:

D=(x2x1)2+(y2y1)2D = \sqrt{ {(x_2 - x_1)}^2 + {(y_2 - y_1)}^2 }


The input will start with NN (1N10001 \le N \le 1000), the number of coordinates. Then NN lines will follow, each with a pair of integers XiX_i and YiY_i (1000Xi,Yi1000-1000 \le X_i, Y_i \le 1000) representing the xx and yy coordinates of the points.


Print the distance between the closest pair from among the given points. Absolute or relative error greater than 10410^{-4} will be ignored.


1 1
2 7
3 5

The two closest points are (2,7)(2, 7) and (3,5)(3, 5). The distance between these two points is 2.23606797749979.