Problem:


Closest Pair

For given n points in metric space, find the distance of the closest points.

Input

n
x0 y0
x1 y1
:
xn-1 yn-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 xi and yi. 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



Sample input:
2
0.0 0.0
1.0 0.0


Sample output:
1.000000

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
from math import hypot
from itertools import takewhile, chain, combinations

def ntp(A: list, axis: int = -1):
    length = len(A)
    if length <= 4:
        return min([hypot(x1 - x2, y1 - y2) for (x1, y1), (x2, y2) in combinations(A, 2)])
    
    x_types = len(set(x for x, _ in A))
    axis1 = 2*x_types <= length
    axis2 = not axis1
    mid_idx = length//2
    
    if axis1 != axis:
        A.sort(key = itemgetter(axis1))
    Al, Ar = A[:mid_idx], A[mid_idx:]
    median = A[mid_idx][axis1]
    
    tmd = min(ntp(Al, axis1), ntp(Ar, axis1))
    
    midA = [p for p in chain(takewhile(lambda t: median - tmd < t[axis1], Al[::-1]),\
                             takewhile(lambda t: median + tmd > t[axis1], Ar))]
    midA.sort(key = itemgetter(axis2))
    for i, (x1, y1) in enumerate(midA):
        ub = (x1, y1)[axis2] + tmd
        for x2, y2 in takewhile(lambda t: t[axis2] < ub, midA[i+1:]):
            tmd = min(tmd, hypot(x1 - x2, y1 - y2))
    
    return tmd
n = int(sys.stdin.readline())
Points = [tuple(map(float, sys.stdin.readline().split())) for _ in [0]*n] 
print('{:.10f}'.format(ntp(Points)))

Submission status: Accepted

Solution code:
# CGL_5_A: Point Set - Closest Pair

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()

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline

import operator


def norm(self):
    return abs(self)

def closest_pair(p):
    m = 0
    p.sort(key=operator.attrgetter('real'))
    d = float('inf')
    for i in range(1, len(p)):
        for j in reversed(range(m, i)):
            tmp = abs(p[j] - p[i])
            if d < tmp.real:
                m += 1
                break
            elif d > tmp:
                d = tmp
    return d



from itertools import combinations
def brute_force(p):
    return min(abs(p[i] - p[j]) for i, j in combinations(range(len(p)), 2))

@profile
def main():
    n = int(readline())
    p = [map(float, readline().split()) for _ in range(n)]
    p = [x + y * 1j for x, y in p]

    
    #print('{:.6f}'.format(brute_force(p)))
    print('{:.6f}'.format(closest_pair(p)))
main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import operator
readline = stdin.readline


def norm(self):
    return abs(self)


def closest_pair(p):
    m = 0
    p.sort(key=operator.attrgetter('real'))
    d = float('inf')
    for i in range(1, len(p)):
        for j in reversed(range(m, i)):
            tmp = p[i] - p[j]
            if d < tmp.real:
                m = j + 1
                break
            tmp = abs(tmp)
            if d > tmp:
                d = tmp
    return d


from itertools import combinations


def brute_force(p):
    return min(abs(p[i] - p[j]) for i, j in combinations(range(len(p)), 2))


@profile
def main():
    n = int(readline())
    p = [map(float, readline().split()) for _ in range(n)]
    p = [x + y * 1j for x, y in p]

    # print('{:.6f}'.format(brute_force(p)))
    print('{:.6f}'.format(closest_pair(p)))
main()

Submission status: Runtime Error

Solution code:
# #### CLOSEST PAIR O(N LOG N) ALGORITHM #### #
# points should be unique, otherwise the closest pair would be the repeated points
# also this will only find 1 pair with the smallest distance, in case there are multiple pairs with this same minimum distance

#import time
#start = time.time()

	
def halve(coord): # split into two halves by x-coordinate
	L = len(coord) # luckily pts are already sorted
	return [coord[:L/2], coord[L/2:]]

def dist(x, y): # for two points x(x0,x1) and y(y0,y1), what is the squared distance? 
	return (x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2
	
def splitpair(px, py, d): # only need to return a correct value if closest pair is split
	xBar = px[(len(px)+1)/2][0]
	Sy = [] # Sy will be the set of points (sorted by Y-coordinate) where the x-coord xi satisfies xBar-d <= xi <= xBar -d
	for i in xrange(len(py)):
		if xBar-d**0.5 <= py[i][0] <= xBar+d**0.5: # only consider a 'strip' around xBar that is 2*sqrt(d) wide
			Sy.append(py[i])	
	
	bestpair = None # the coords of the best pair of points so far
	bestD = d # the squared distance of the best pair of points
	# now iterate through Sy for points that aren't more than 7 apart
	for i in xrange(len(Sy)-2):
		for j in xrange(1, min(8, len(Sy)-i-1)):  # 7 next points
			p, q = Sy[i], Sy[i+j]
			
			if dist(p, q) < bestD:
				bestpair = [p, q]
				bestD = dist(p, q)
				
	return bestpair
	
def convert(p1, p2): # convert 2 points into two pairs of pairs, first sorted by x, other sorted by y1
	return [sorted([p1, p2]), sorted([p1, p2], key=lambda x: x[1])]
	
def solve(Px, Py): # where Px and Py are the points sorted by x and y coordinate respectively
	# this function returns two closest points
	assert len(Px) == len(Py) # make sure you have the same number of x and y coords
	if len(Px) == 2:
		return (Px, Py)
	elif len(Px) == 3: # 3 points, brute force
		p1, p2, p3 = [x for x in Px]
		d12, d13, d23 = dist(p1, p2), dist(p1, p3), dist(p2, p3)
		if min(d12, d13, d23) == d12: 
			return convert(p1, p2)
		elif min(d12, d13, d23) == d13: 
			return convert(p1, p3)
		else: 
			return convert(p2, p3)
	else:
		Qx, Rx = [x for x in halve(Px)]
		Qy, Ry = [], []
		k = Qx[-1][0]
		for pt in Py:
			if pt[0] <= k:
				Qy.append(pt)
			else:
				Ry.append(pt)
		
		assert len(Qx) == len(Qy)
		assert len(Rx) == len(Ry)
		
		# now use recursion. note ci is of the form [[x1,x2], [y1,y2]]
		c1 = solve(Qx, Qy) # find the closest pair in left half
		c2 = solve(Rx, Ry) # find the closest pair in the right half
		
		D = min(dist(c1[0][0], c1[0][1]), dist(c2[0][0], c2[0][1]))
		if D == dist(c1[0][0], c1[0][1]):
			bestpair = c1
		elif D == dist(c2[0][0], c2[0][1]):
			bestpair = c2
		
		c3 = splitpair(Px, Py, D) # find the closest split pair. this needs to be O(n) to get O(n log n) for entire algo
		
		if c3 is not None: 
			return convert(c3[0], c3[1])
		else:
			return bestpair # else it's one of the c1 or c2
		
		
def main():
	N = int(raw_input().split()[0]) # N is number of points
	assert  N >= 2
	pts = [] # pairs of points, i.e pts = [[x1,y1], [x2,y2], ... , [xn,yn]]
	
	# get all pairs of points into our list
	for i in xrange(N):
		pts.append([float(x) for x in raw_input().split()])
		
	
	Px = sorted(pts) # sort the pts by x coordinate
	Py = sorted(pts, key=lambda x: x[1]) # sort the pts by y coordinate
	
	res = solve(Px, Py)
	
	'''
	# find the index of the points in pts
	for i in xrange(len(pts)):
		if pts[i] == res[0][0]:
			ind1 = i
		elif pts[i] == res[0][1]:
			ind2 = i
			
	d = dist(pts[ind1], pts[ind2]) ** 0.5
	'''
	
	print dist(res[0][0], res[0][1]) ** 0.5

if __name__ == '__main__':
	main()


#print "%.2f %s" % (((time.time() - start) * 1000), "ms")

Submission status: Runtime Error

Solution code:
# #### CLOSEST PAIR O(N LOG N) ALGORITHM #### #
# points should be unique, otherwise the closest pair would be the repeated points
# also this will only find 1 pair with the smallest distance, in case there are multiple pairs with this same minimum distance

#import time
#start = time.time()

	
def halve(coord): # split into two halves by x-coordinate
	L = len(coord) # luckily pts are already sorted
	return [coord[:L/2], coord[L/2:]]

def dist(x, y): # for two points x(x0,x1) and y(y0,y1), what is the squared distance? 
	return (x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2
	
def splitpair(px, py, d): # only need to return a correct value if closest pair is split
	xBar = px[(len(px)+1)/2][0]
	Sy = [] # Sy will be the set of points (sorted by Y-coordinate) where the x-coord xi satisfies xBar-d <= xi <= xBar -d
	for i in xrange(len(py)):
		if xBar-d**0.5 <= py[i][0] <= xBar+d**0.5: # only consider a 'strip' around xBar that is 2*sqrt(d) wide
			Sy.append(py[i])	
	
	bestpair = None # the coords of the best pair of points so far
	bestD = d # the squared distance of the best pair of points
	# now iterate through Sy for points that aren't more than 7 apart
	for i in xrange(len(Sy)-2):
		for j in xrange(1, min(8, len(Sy)-i-1)):  # 7 next points
			p, q = Sy[i], Sy[i+j]
			
			if dist(p, q) < bestD:
				bestpair = [p, q]
				bestD = dist(p, q)
				
	return bestpair
	
def convert(p1, p2): # convert 2 points into two pairs of pairs, first sorted by x, other sorted by y1
	return [sorted([p1, p2]), sorted([p1, p2], key=lambda x: x[1])]
	
def solve(Px, Py): # where Px and Py are the points sorted by x and y coordinate respectively
	# this function returns two closest points
	assert len(Px) == len(Py) # make sure you have the same number of x and y coords
	if len(Px) == 2:
		return (Px, Py)
	elif len(Px) == 3: # 3 points, brute force
		p1, p2, p3 = [x for x in Px]
		d12, d13, d23 = dist(p1, p2), dist(p1, p3), dist(p2, p3)
		if min(d12, d13, d23) == d12: 
			return convert(p1, p2)
		elif min(d12, d13, d23) == d13: 
			return convert(p1, p3)
		else: 
			return convert(p2, p3)
	else:
		Qx, Rx = [x for x in halve(Px)]
		Qy, Ry = [], []
		k = Qx[-1][0]
		for pt in Py: # this is linear time, you loop through Py exactly once
			if pt[0] <= k and len(Qy) < len(Qx):
				Qy.append(pt)
			else:
				Ry.append(pt)
		
		assert len(Qx) == len(Qy)
		assert len(Rx) == len(Ry)
		
		# now use recursion. note ci is of the form [[x1,x2], [y1,y2]]
		c1 = solve(Qx, Qy) # find the closest pair in left half
		c2 = solve(Rx, Ry) # find the closest pair in the right half
		
		D = min(dist(c1[0][0], c1[0][1]), dist(c2[0][0], c2[0][1]))
		if D == dist(c1[0][0], c1[0][1]):
			bestpair = c1
		elif D == dist(c2[0][0], c2[0][1]):
			bestpair = c2
		
		c3 = splitpair(Px, Py, D) # find the closest split pair. this needs to be O(n) to get O(n log n) for entire algo
		
		if c3 is not None: 
			return convert(c3[0], c3[1])
		else:
			return bestpair # else it's one of the c1 or c2
		
		
def main():
	N = int(raw_input().split()[0]) # N is number of points
	assert  N >= 2
	pts = [] # pairs of points, i.e pts = [[x1,y1], [x2,y2], ... , [xn,yn]]
	
	# get all pairs of points into our list
	for i in xrange(N):
		pts.append([float(x) for x in raw_input().split()])
		
	
	Px = sorted(pts) # sort the pts by x coordinate
	Py = sorted(pts, key=lambda x: x[1]) # sort the pts by y coordinate
	
	res = solve(Px, Py)
	
	'''
	# find the index of the points in pts
	for i in xrange(len(pts)):
		if pts[i] == res[0][0]:
			ind1 = i
		elif pts[i] == res[0][1]:
			ind2 = i
			
	d = dist(pts[ind1], pts[ind2]) ** 0.5
	'''
	
	print dist(res[0][0], res[0][1]) ** 0.5

if __name__ == '__main__':
	main()


#print "%.2f %s" % (((time.time() - start) * 1000), "ms")

Submission status: Runtime Error

Solution code:
import itertools

def _get_min_distance(points):
    min_d = 400
    for p1, p2 in itertools.combinations(points, 2):
        min_d = min(min_d, abs(p1 - p2))
    return min_d

# Search based on x axis
def closest_pair_distance_x(points):
    n = len(points)
    if n <= 3:
        return _get_min_distance(points)
    else:
        mid = n // 2
        left_points = points[:mid]
        right_points = points[mid:]
        d_Lmin = closest_pair_distance(left_points)
        d_Rmin = closest_pair_distance(right_points)
        dist = min(d_Lmin, d_Rmin)
        min_d = dist
        for lp in left_points[::-1]:
            if right_points[0].real - lp.real >= dist:
                break
            for rp in right_points:
                if rp.real -lp.real >= dist:
                    break
                if lp.imag - dist < rp.imag < lp.imag + dist:
                    min_d = min(min_d, abs(lp - rp))
        return min_d

# Search based on y axis
def closest_pair_distance_y(points):
    n = len(points)
    if n <= 3:
        return _get_min_distance(points)
    else:
        mid = n // 2
        lower_points = points[:mid]
        upper_points = points[mid:]
        d_Lmin = closest_pair_distance(lower_points)
        d_Umin = closest_pair_distance(upper_points)
        dist = min(d_Lmin, d_Umin)
        min_d = dist
        for lp in lower_points[::-1]:
            if upper_points[0].imag - lp.imag >= dist:
                break
            for up in upper_points:
                if up.imag -lp.imag >= dist:
                    break
                if lp.real - dist < up.real < lp.real + dist:
                    min_d = min(min_d, abs(lp - up))
        return min_d

# Acceptance of input
def string_to_complex(s):
    x, y = map(float, s.split())
    return x + y * 1j

import sys

file_input = sys.stdin

n = int(file_input.readline())

P = [string_to_complex(line) for line in file_input]

# Solve
P.sort(key = lambda c: (c.real, c.imag))

if P[-1].real - P[0].real >= P[-1].imag - P[0].imag:
    ans = closest_pair_distance_x(P)
    print('{:f}'.format(ans))
else:
    P.sort(key = lambda c: c.imag)
    ans = closest_pair_distance_y(P)
    print('{:f}'.format(ans))

Submission status: Runtime Error

Solution code:
from operator import attrgetter
from itertools import combinations

keys = [attrgetter('real'), attrgetter('imag')]


def solve(points, axis):
    l = len(points)
    if l < 20:
        return min(abs(p2 - p1) for p1, p2 in combinations(points, 2))
    m = n // 2
    pl, pr = points[:m], points[m:]
    key, rkey = keys[axis], keys[not axis]
    ans = min(solve(sorted(pl, key=rkey), not axis),
              solve(sorted(pr, key=rkey), not axis))
    pm = key(pr[0])
    for p in reversed(pl):
        if key(p) <= pm - ans:
            break
        for q in pr:
            if key(q) >= pm + ans:
                break
            rp = rkey(p)
            if rp - ans < rkey(q) < rp + ans:
                ans = min(ans, abs(q - p))
    return ans


n = int(input())
points = [complex(*map(float, input().split())) for _ in range(n)]
print(solve(sorted(points, key=keys[0]), 0))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

from operator import attrgetter
from itertools import combinations

keys = [attrgetter('real'), attrgetter('imag')]


def solve(points, axis):
    l = len(points)
    if l < 20:
        return min(abs(p2 - p1) for p1, p2 in combinations(points, 2))
    m = n // 2
    pl, pr = points[:m], points[m:]
    key, rkey = keys[axis], keys[not axis]
    ans = min(solve(sorted(pl, key=rkey), not axis),
              solve(sorted(pr, key=rkey), not axis))
    pm = key(pr[0])
    for p in reversed(pl):
        if key(p) <= pm - ans:
            break
        for q in pr:
            if key(q) >= pm + ans:
                break
            rp = rkey(p)
            if rp - ans < rkey(q) < rp + ans:
                ans = min(ans, abs(q - p))
    return ans


n = int(input())
points = [complex(*map(float, input().split())) for _ in range(n)]
print(solve(sorted(points, key=keys[0]), 0))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = []
for i in range(n):
    p.append(tuple(map(float,input().split())))
d = []
min = 999999999999
for i in range(n-1):
    for j in range(i+1,n):
        a = ((p[j][0]-p[i][0])**2+(p[j][1]-p[i][1])**2)
        if a < min:
            min = a

print(round(np.sqrt(min),11))