Problem:
Closest Pair For given n points in metric space, find the distance of the closest points. Input  n  x 0  y 0  x 1  y 1 : x n-1  y n-1  The first integer n is the number of points. In the following n lines, the coordinate of the i -th point is given by two real numbers x i and y i . Each value is a real number with at most 6 digits after the decimal point. Output Print the distance in a line. The output values should be in a decimal fraction with an error less than 0.000001. Constraints  2 ≤ n ≤ 100,000  -100 ≤ x , y ≤ 100  Sample Input 1 2
0.0 0.0
1.0 0.0 Sample Output 1 1.000000 Sample Input 2 3
0.0 0.0
2.0 0.0
1.0 1.0 Sample Output 2 1.41421356237

Solution (Python):


from operator import itemgetter
from math import sqrt


def closest_distance(ps):
    def split(i, j):
        if j - i < 2:
            return float('INF')
        mid = (i + j) // 2
        d = min(split(i, mid), split(mid, j))
        lv, rv = ps[mid][0]-d, ps[mid][0]+d
        return merge(sorted([p for p in ps[i:j] if lv <= p[0] <= rv],
                            key=itemgetter(1)), d)

    def merge(_ps, d):
        n = len(_ps)
        for i in range(n-1):
            for j in range(i+1, n):
                if d < _ps[j][1] - _ps[i][1]:
                    break
                d = min(d, distance(_ps[i], _ps[j]))

        return d

    ps.sort(key=itemgetter(0, 1))
    return split(0, len(ps))


def dot(p0, p1):
    x0, y0 = p0
    x1, y1 = p1
    return x0*x1 + y0*y1


def distance(p0, p1):
    x0, y0 = p0
    x1, y1 = p1
    return sqrt((x1-x0)**2 + (y1-y0)**2)


def run():
    n = int(input())
    ps = []

    for _ in range(n):
        x, y = [float(i) for i in input().split()]
        ps.append((x, y))

    print("{:.10f}".format(closest_distance(ps)))


if __name__ == '__main__':
    run()