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: Time Limit Exceeded

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 = [], []
		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: Time Limit Exceeded

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 "%.10f" % (dist(res[0][0], res[0][1]) ** 0.5)

if __name__ == '__main__':
	main()


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

Submission status: Time Limit Exceeded

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)+1)/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: Time Limit Exceeded

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("{0:.6f}".format(min_distance))

Submission status: Time Limit Exceeded

Solution code:
import statistics

def func_x(point_list_in):
    min_sum_square = float("inf")
    point_list = sorted(point_list_in, key=lambda point: point[0])
    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)
    return min_sum_square**0.5

def func_y(point_list_in):
    min_sum_square = float("inf")
    point_list = sorted(point_list_in, key=lambda point: point[1])
    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 y_dif <=0 and y_dif_square >= min_sum_square:
                break
            else:
                sum_square = x_dif_square + y_dif_square
                min_sum_square = min(sum_square, min_sum_square)
    return min_sum_square**0.5

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])]
x_list = [point[0] for point in point_list]
y_list = [point[1] for point in point_list]
x_var = statistics.pvariance(x_list)
y_var = statistics.pvariance(y_list)

if x_var > y_var:
    min_distance = func_x(point_list)
else:
    min_distance = func_y(point_list)
print("{0:.6f}".format(min_distance))

Submission status: Time Limit Exceeded

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 = 400

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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_x(left_points)
        d_Rmin = closest_pair_distance_x(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_y(lower_points)
        d_Umin = closest_pair_distance_y(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: Time Limit Exceeded

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_x(left_points)
        d_Rmin = closest_pair_distance_x(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_y(lower_points)
        d_Umin = closest_pair_distance_y(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.imag)
ans = closest_pair_distance_y(P)
print('{:f}'.format(ans))

Submission status: Time Limit Exceeded

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_x(left_points)
        d_Rmin = closest_pair_distance_x(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_y(lower_points)
        d_Umin = closest_pair_distance_y(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
import sys

file_input = sys.stdin

n = int(file_input.readline())

P = []
pX = []
pY = []

for line in file_input:
    x, y = map(float, line.split())
    P.append(x + y * 1j)
    pX.append(x)
    pY.append(y)

# Solve
if len(set(pX)) > len(set(pY)):
    P.sort(key = lambda c: c.real)
    ans = closest_pair_distance_x(P)
else:
    P.sort(key = lambda c: c.imag)
    ans = closest_pair_distance_y(P)

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

Submission status: Time Limit Exceeded

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('{:.10f}'.format(solve(sorted(points, key=keys[0]), 0)))

Submission status: Time Limit Exceeded

Solution code:
from operator import attrgetter
from itertools import combinations

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


def bound(points):
    xmx = max(p.real for p in points)
    xmn = min(p.real for p in points)
    ymx = max(p.imag for p in points)
    ymn = min(p.imag for p in points)
    return xmx - xmn < ymx - ymn


def solve(points, prev_sort):
    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[prev_sort], keys[not prev_sort]
    pl_next_sort, pr_next_sort = bound(pl), bound(pr)
    pl_next_points = pl.copy() if prev_sort == pl_next_sort else sorted(pl, key=keys[pl_next_sort])
    pr_next_points = pr.copy() if prev_sort == pr_next_sort else sorted(pr, key=keys[pr_next_sort])
    ans = min(solve(pl_next_points, pl_next_sort), solve(pr_next_points, pr_next_sort))
    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('{:.10f}'.format(solve(sorted(points, key=keys[0]), 0)))

Submission status: Time Limit Exceeded

Solution code:
from operator import attrgetter
from itertools import combinations

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


def bound(points):
    # xmx = max(p.real for p in points)
    # xmn = min(p.real for p in points)
    # ymx = max(p.imag for p in points)
    # ymn = min(p.imag for p in points)
    # return xmx - xmn < ymx - ymn
    xs, ys = {p.real for p in points}, {p.imag for p in points}
    return len(xs) < len(ys)


def solve(points, prev_sort):
    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[prev_sort], keys[not prev_sort]
    pl_next_sort, pr_next_sort = bound(pl), bound(pr)
    pl_next_points = pl.copy() if prev_sort == pl_next_sort else sorted(pl, key=keys[pl_next_sort])
    pr_next_points = pr.copy() if prev_sort == pr_next_sort else sorted(pr, key=keys[pr_next_sort])
    ans = min(solve(pl_next_points, pl_next_sort), solve(pr_next_points, pr_next_sort))
    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('{:.10f}'.format(solve(sorted(points, key=keys[0]), 0)))

Submission status: Time Limit Exceeded

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

print(round(min,11))

Submission status: Time Limit Exceeded

Solution code:
import math as m
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(m.sqrt(min),11))

Submission status: Time Limit Exceeded

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("{:.10f}".format(math.sqrt(solve(a)/(m**2))))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt

def solve(a: list):
    length = len(a)
    if length <= 3:
        return min(sqrt((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, sqrt((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("{:.10f}".format(solve(a)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
from itertools import permutations
from math import sqrt

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

    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)
    for p in x_r:
        if p[0] > median_x+delta:
            break
        m_a.append(p)
    m_a.sort(key=itemgetter(1))

    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, sqrt((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("{:.10f}".format(solve(a)))