The problem
Given at least two points (x, y) with whole-number coordinates, return a pair of positions (i, j), with i != j, of two points that are closest together. If several pairs are equally close, return any of them.
closest_pair([(0, 0), (5, 1), (1, 1), (9, 9)])
# (0, 2), or (2, 0)
Compare squared distances, dx * dx + dy * dy: they stay whole numbers, so there is no rounding. Two positions may hold the same point; their distance is 0. The tests check that your two positions are different and that their squared distance is the smallest possible.
Limits
- Up to 40,000 points, with coordinates up to about 50 million. Many points may have the same x. Aim for O(n log n).
Builds on DVCQ-4 Closest pair of points.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Two points | Not run | |
| 3 | The same point twice | Not run | |
| 4 | On a horizontal line | Not run | |
| 5 | Negative coordinates | Not run | |
| 6 | Across the middle | Not run | |
| 7 | A grid and one more point | Not run | |
| 8 | 40,000 scattered points | Not run | |
| 9 | 30,000 points on a vertical line | Not run |