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) y = int(line) p = (x, y) P.append(p) print(closest(P, n)) def square(x): return x * x def square_distance(p0, p1): return square(p0 - p1) + square(p0 - p1) 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, P) if n == 3: return min(square_distance(P, P), square_distance(P, P), square_distance(P, P)) 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] strip =  strip_length = 0 for i in range(n): p = P[i] if abs(p - mid_x) < closest_distance_so_far: strip.append(p) strip_length += 1 strip.sort(key=lambda x: x) # 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?