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: Wrong Answer

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


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: Wrong Answer

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 isinstance(p[0], int) == False: print "1"
			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 = [], []
		for pt in Py:
			if pt in Qx:
				Qy.append(pt)
			if pt in Rx:
				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: Wrong Answer

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 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] #x-coordinate of the leftmost element of px
	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:
		L = len(Px)
		Qx, Rx = Px[:(L+1)/2], Px[(L+1)/2:]
		assert abs(len(Qx) - len(Rx)) <= 1
		Qy, Ry = [], []
		k = Qx[-1][0] # x-coordinate of the rightmost element in Qx
		dump = []
		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)
			elif pt[0] == k: # if it's equal, keep track of these, then add back the correct number
				dump.append(pt)
			else:
				Ry.append(pt)
		# now add back enough of the 'dump' list
		diff = len(Qx) - len(Qy)
		for d in dump[:diff]:
			Qy.append(d)
		for d in dump[diff:]:
			Ry.append(d)
		
		# now use recursion. note ci is of the form [[x1,x2], [y1,y2]]
		if not sorted(Qx) == sorted(Qy):
			print Qx
			print Qy
		assert sorted(Rx) == sorted(Ry)
		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:
			assert sorted(bestpair[0]) == sorted(bestpair[1])
			return [bestpair[0], bestpair[1]] # 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: Wrong Answer

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 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] #x-coordinate of the leftmost element of px
	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:
		L = len(Px)
		Qx, Rx = Px[:L/2], Px[L/2:]
		assert abs(len(Qx) - len(Rx)) <= 1
		Qy, Ry = [], []
		k = Qx[-1][0] # x-coordinate of the rightmost element in Qx
		dump = []
		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)
			elif pt[0] == k: # if it's equal, keep track of these, then add back the correct number
				dump.append(pt)
			else:
				Ry.append(pt)
		# now add back enough of the 'dump' list
		diff = len(Qx) - len(Qy)
		for d in dump[:diff]:
			Qy.append(d)
		for d in dump[diff:]:
			Ry.append(d)
		
		# now use recursion. note ci is of the form [[x1,x2], [y1,y2]]
		if not sorted(Qx) == sorted(Qy):
			print Qx
			print Qy
		assert sorted(Rx) == sorted(Ry)
		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:
			assert sorted(bestpair[0]) == sorted(bestpair[1])
			return [bestpair[0], bestpair[1]] # 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: Wrong Answer

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 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 value if closest pair is split between left and right halves
	xBar = px[len(px)/2][0] # large x-coordinate of the left half of px
	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]) # if exists a pair with dist less than d, it must be in this strip (obvious)	
	
	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
	# if a pair exists that is closer than dist d, it must be within 7 of each other
	# ask me for proof if you haven't seen this observation before it's pretty cool
	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 y
	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
	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:
		# split the left and right halves of all points (by x coord)
		L = len(Px)
		Qx, Rx = Px[:L/2], Px[L/2:]
		Qy, Ry = [], []
		k, l = Qx[-1][0], Qx[-1][1] # x and y coords of the rightmost element in Qx
		for pt in Py: # this is linear time, you loop through Py exactly once.
			# need this in order 
			if pt[0] < k:
				Qy.append(pt)
			elif pt[0] == k:
				if pt[1] <= l:
					Qy.append(pt)
				else:
					Ry.append(pt)
			else:
				Ry.append(pt)
		
		# 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])) # get the min distance of both of these to solve split case
		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[0], bestpair[1]] # else it's one of the c1 or c2
		
		
def main():
	N = int(raw_input().split()[0]) # N is number of points
	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) # keep one copy sorted by x coord, the other sorted by y coord to keep the split in half in linear time
	
	print "%.10f" % (dist(res[0][0], res[0][1]) ** 0.5)
	
if __name__ == '__main__':
	main()


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

Submission status: Wrong Answer

Solution code:
num_point = int(input())
point_list = [0] * num_point
for i in range(num_point):
    line_split = input().split(" ")
    point_list[i] = [float(line_split[0]), float(line_split[1])]

min_sum_square = float("inf")
for i in range(num_point):
    for j in range(i + 1, num_point):
        x_dif = point_list[i][0] - point_list[j][0]
        y_dif = point_list[i][1] - point_list[j][1]
        if x_dif < min_sum_square and y_dif < min_sum_square:
            sum_square = x_dif**2 + y_dif**2
            if sum_square < min_sum_square:
                min_sum_square = sum_square
        else:
            continue

min_distance = min_sum_square**0.5
print(min_distance)

Submission status: Wrong Answer

Solution code:
num_point = int(input())
point_list = [0] * num_point
for i in range(num_point):
    line_split = input().split(" ")
    point_list[i] = [float(line_split[0]), float(line_split[1])]
point_list.sort(key=lambda point: point[0])

min_sum_square = float("inf")
for i in range(num_point):
    for j in range(i + 1, num_point):
        x_dif = point_list[i][0] - point_list[j][0]
        y_dif = point_list[i][1] - point_list[j][1]
        x_dif_square = x_dif**2
        y_dif_square = y_dif**2
        if x_dif <=0 and x_dif_square >= min_sum_square:
            break
        else:
            sum_square = x_dif_square + y_dif_square
            min_sum_square = min(sum_square, min_sum_square)

min_distance = min_sum_square**0.5
print(min_distance)

Submission status: Wrong Answer

Solution code:
from math import sqrt
n = input()
ps = [map(float, raw_input().split()) for i in xrange(n)]
ps.sort()
INF = 10**9

def cp_rec(ps, i, n):
    if n <= 1:
        return INF, [ps[i]]
    m = n/2
    x = ps[i+m][0]
    d1, qs1 = cp_rec(ps, i, m)
    d2, qs2 = cp_rec(ps, i+m, n-m)
    d = min(d1, d2)
    # merge
    qs = [None]*n
    s = t = idx = 0
    while s < m and t < n-m:
        if qs1[s][1] < qs2[t][1]:
            qs[idx] = qs1[s]; s += 1
        else:
            qs[idx] = qs2[t]; t += 1
        idx += 1
    while s < m:
        qs[idx] = qs1[s]; s += 1
        idx += 1
    while t < n-m:
        qs[idx] = qs2[t]; t += 1
        idx += 1
    b = []
    for i in xrange(n):
        ax, ay = ps[i]
        if abs(ax - x) >= d:
            continue
        for j in xrange(len(b)-1, -1, -1):
            dx = ax - b[j][0]
            dy = ay - b[j][1]
            if dy >= d:
                break
            d = min(d, sqrt(dx**2 + dy**2))
        b.append(ps[i])
    return d, qs
def closest_pair(ps):
    n = len(ps)
    return cp_rec(ps, 0, n)[0]
print closest_pair(ps)

Submission status: Wrong Answer

Solution code:
import sys

file_input = sys.stdin

n = file_input.readline()

def distance(s_p1, s_p2):
    x1, y1 = map(float, s_p1.split())
    x2, y2 = map(float, s_p2.split())
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

import itertools

min_d = 200

for p1, p2 in itertools.combinations(file_input, 2):
    min_d = min(min_d, distance(p1, p2))

print('{:f}'.format(min_d))

Submission status: Wrong Answer

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

def closest_pair_distance(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

# 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]

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

# Output
ans = closest_pair_distance(P)
print('{:f}'.format(ans))

Submission status: Wrong Answer

Solution code:
import itertools

def _get_distance(p1, p2):
    return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

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

def closest_pair_distance(points, axis):
    # axis: x; 0, y; 1
    n = len(points)
    if n <= 3:
        return _get_min_distance(points)
    else:
        mid = n // 2
        px, py = zip(*points)
        if len(set(px)) > len(set(py)):
            if axis:
                points.sort(key = lambda p: p[0])
                axis = 0
        elif not axis:
            points.sort(key = lambda p: p[1])
            axis = 1
        A_points = points[:mid]
        B_points = points[mid:]
        d_Amin = closest_pair_distance(A_points, axis)
        d_Bmin = closest_pair_distance(B_points, axis)
        dist = min(d_Amin, d_Bmin)
        min_d = dist
        for ap in A_points[::-1]:
            if B_points[0][axis] - ap[axis] >= dist:
                break
            for bp in B_points:
                if bp[axis] - ap[axis] >= dist:
                    break
                if ap[not axis] - dist < bp[not axis] < ap[not axis] + dist:
                    min_d = min(min_d, _get_distance(ap, bp))
        return min_d


# Acceptance of input
import sys

file_input = sys.stdin

n = int(file_input.readline())

P = [tuple(map(float, line.split())) for line in file_input]

# Solve
P.sort(key = lambda p: p[0])
ans = closest_pair_distance(P, 0)

print('{:f}'.format(ans))

Submission status: Wrong Answer

Solution code:
import itertools

def _get_distance(p1, p2):
    return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

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

def closest_pair_distance(points):
    n = len(points)
    if n <= 3:
        return _get_min_distance(points)
    else:
        mid = n // 2
        px, py = zip(*points)
        if len(set(px)) > len(set(py)):
            points.sort(key = lambda p: p[0])
            # axis: x; 0, y; 1
            axis1 = 0
            axis2 = 1
        else:
            points.sort(key = lambda p: p[1])
            axis1 = 1
            axis2 = 0
        A_points = points[:mid]
        B_points = points[mid:]
        d_Amin = closest_pair_distance(A_points)
        d_Bmin = closest_pair_distance(B_points)
        dist = min(d_Amin, d_Bmin)
        min_d = dist
        for ap in A_points[::-1]:
            if B_points[0][axis1] - ap[axis1] >= dist:
                break
            for bp in B_points:
                if bp[axis1] - ap[axis1] >= dist:
                    break
                if ap[axis2] - dist < bp[axis2] < ap[axis2] + dist:
                    min_d = min(min_d, _get_distance(ap, bp))
        return min_d

# Acceptance of input
import sys

file_input = sys.stdin

n = int(file_input.readline())

P = [tuple(map(float, line.split())) for line in file_input]

# Solve
ans = closest_pair_distance(P)

print('{:f}'.format(ans))

Submission status: Wrong Answer

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 = l // 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: Wrong Answer

Solution code:
import sys
import math

def solve(a: list):
    length = len(a)
    if length <= 3:
        return min((p1[0]-p2[0])**2+(p1[1]-p2[1])**2 for p1, p2 in zip(a, a[1:]))

    med = length//2
    x_l, x_r = a[:med], a[med:]
    delta = min(solve(x_l), solve(x_r))
    median_x = a[med][0]
    m_a = []
        
    for p in x_l[::-1]:
        if p[0] < median_x-delta:
            break
        m_a.append(p)
    m_a.reverse()
    for p in x_r:
        if p[0] > median_x+delta:
            break
        m_a.append(p)

    for i, (x1, y1) in enumerate(m_a):
        to_y = y1 + delta
        for j, (x2, y2) in enumerate(m_a[i+1:]):
            if y2 > to_y:
                break
            delta = min(delta, (x1-x2)**2+(y1-y2)**2)

    return delta

if __name__ == "__main__":
    N = int(input())
    a = sorted([tuple(map(float, l.split())) for l in sys.stdin.readlines()])
    print(math.sqrt(solve(a)))

Submission status: Wrong Answer

Solution code:
import sys
import math

def solve(a: list):
    length = len(a)
    if length <= 3:
        return min((p1[0]-p2[0])**2+(p1[1]-p2[1])**2 for p1, p2 in zip(a, a[1:]))

    med = length//2
    x_l, x_r = a[:med], a[med:]
    delta = min(solve(x_l), solve(x_r))
    median_x = a[med][0]
    m_a = []
        
    for p in x_l[::-1]:
        if p[0] < median_x-delta:
            break
        m_a.append(p)
    m_a.reverse()
    for p in x_r:
        if p[0] > median_x+delta:
            break
        m_a.append(p)

    for i, (x1, y1) in enumerate(m_a):
        to_y = y1 + delta
        for j, (x2, y2) in enumerate(m_a[i+1:]):
            if y2 > to_y:
                break
            delta = min(delta, (x1-x2)**2+(y1-y2)**2)

    return delta

if __name__ == "__main__":
    N = int(input())
    m = 1000000
    a = sorted([tuple(map(lambda s: int(float(s)*m), l.split())) for l in sys.stdin.readlines()])
    print(math.sqrt(solve(a)/(m**2)))

Submission status: Wrong Answer

Solution code:
import sys
import math

def solve(a: list):
    length = len(a)
    if length <= 3:
        return min((p1[0]-p2[0])**2+(p1[1]-p2[1])**2 for p1, p2 in zip(a, a[1:]))

    med = length//2
    x_l, x_r = a[:med], a[med:]
    delta = min(solve(x_l), solve(x_r))
    median_x = a[med][0]
    m_a = []
        
    for p in x_l[::-1]:
        if p[0] < median_x-delta:
            break
        m_a.append(p)
    m_a.reverse()
    for p in x_r:
        if p[0] > median_x+delta:
            break
        m_a.append(p)

    for i, (x1, y1) in enumerate(m_a):
        to_y = y1 + delta
        for j, (x2, y2) in enumerate(m_a[i+1:]):
            if y2 > to_y:
                break
            delta = min(delta, (x1-x2)**2+(y1-y2)**2)

    return delta

if __name__ == "__main__":
    N = int(input())
    m = 1000000
    a = sorted([tuple(map(lambda s: int(float(s)*m), l.split())) for l in sys.stdin.readlines()])
    print("{:f}".format(math.sqrt(solve(a)/(m**2))))

Submission status: Time Limit Exceeded

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


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

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

Submission status: Time Limit Exceeded

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


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