A harbour master logs the positions of mooring buoys as integer grid points (x, y).
Two buoys that are too close can tangle their lines, so she wants the distance between the
closest two. Write nearest_buoys(points) returning the squared straight-line distance
(x1 - x2)**2 + (y1 - y2)**2 of the closest pair of different list entries. Two entries
may share the same position, giving 0.
Examples
Input: points = [(0, 0), (5, 4), (9, 9), (6, 1), (2, 7)]
Output: 10
Explanation: (5, 4) and (6, 1) are 1 apart in x and 3 in y: 1 + 9 = 10.
Input: points = [(3, 3), (-2, 8), (3, 3)]
Output: 0
Constraints
2 <= len(points) <= 20000-10**6 <= x, y <= 10**6- Checking every pair is far too slow for the largest inputs.
Goals
- Split a point set by x-coordinate and solve each half recursively
- Combine the halves by checking only a narrow strip around the dividing line
- Merge the halves by y as in merge sort so the strip needs no extra sorting