In a course I'm doing, I was given the task of finding the closest pair of points among the given points. The program that passed all test cases was the following:
import math
if __name__ == '__main__':
n = int(input())
P = []
for i in range(n):
line = input().split()
x = int(line[0])
y = int(line[1])
p = (x, y)
P.append(p)
print(closest(P, n))
def square(x):
return x * x
def square_distance(p0, p1):
return square(p0[0] - p1[0]) + square(p0[1] - p1[1])
def closest(P, n):
P.sort() # sort by x coordinates
return math.sqrt(_closest_square_distance(P, n))
def _closest_square_distance(P, n):
if n == 2:
return square_distance(P[0], P[1])
if n == 3:
return min(square_distance(P[0], P[1]), square_distance(P[0], P[2]), square_distance(P[1], P[2]))
mid = n // 2
dl = _closest_square_distance(P[:mid], mid)
dr = _closest_square_distance(P[mid:], n - mid)
closest_square_distance = min(dl, dr)
closest_distance_so_far = math.sqrt(closest_square_distance)
mid_x = P[mid][0]
strip = []
strip_length = 0
for i in range(n):
p = P[i]
if abs(p[0] - mid_x) < closest_distance_so_far:
strip.append(p)
strip_length += 1
strip.sort(key=lambda x: x[1]) # sort strip by y coordinates
for i in range(strip_length):
js = min(strip_length, i + 7) # sufficient to compute next 6 neighbors
for j in range(i + 1, js):
ds = square_distance(strip[i], strip[j])
if ds < closest_square_distance:
closest_square_distance = ds
return closest_square_distance
This code was based on the algorithm found at https://en.wikipedia.org/wiki/Closest_pair_of_points_problem#Planar_case . What do you think I can do better? Is there a more efficient way to implement this algorithm? (In this one, I just tried to delay the sqrt
computation as long as possible, and avoided to calculate len
where I could). Is there an even more efficient algorithm?