Closest Pair of Stars

A star chart lists stars as (x, y) tuples of integers. Write closest_pair(points) that returns the smallest squared distance between two different entries of the list: the smallest value of (x1 - x2) ** 2 + (y1 - y2) ** 2 over all pairs. The same position can appear twice, and then the answer is 0.

Squared distances are whole numbers, so no square root is needed and the answer is an exact integer.

Examples

closest_pair([(0, 0), (5, 5), (1, 2), (9, 0)])   # returns 5
closest_pair([(3, 3), (-3, -3)])                 # returns 72
closest_pair([(4, 1), (7, 8), (4, 1)])           # returns 0

In the first chart, (0, 0) and (1, 2) are closest: 1 * 1 + 2 * 2 = 5.

Constraints

• 2 to 20,000 points.
• Coordinates are between -109 and 109.
• Comparing every pair means about 200 million comparisons for 20,000 points, which is far too slow: aim for about n log n.