The two closest towns
A gazetteer of settlements has tens of thousands of records with coordinates. Before publication the editor checks whether some of them are suspiciously close: two records of one place, or a city and its own district. The editor wants to start with the closest pair. Given points on a plane, find the smallest distance between two of them.
The second and third tests are the 45,227 cities of the world with 10 thousand people or more from the GeoNames gazetteer, as points (longitude, latitude) in thousandths of a degree, ignoring the fact that the Earth is round: in the second test all records as they are, in the third each point kept once.
Input
The first line holds the number of points n (2 ≤ n ≤ 100,000), then n lines with coordinates x y, integers, |x|, |y| ≤ 10⁹. Points may coincide.
Output
The square of the smallest distance between two points, an integer.
Examples
Example 1
6 0 0 7 1 3 4 10 10 6 5 -2 9
10
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Trying all pairs is up to 5·10⁹ distances. Pairs have to be cut off without computing them. Cut the points with a vertical line into two equal halves and solve each. Which pairs remain unchecked?
2Hint 2
Let d be the best distance inside the halves. A pair across the cut closer than d can only be in a strip 2d wide around the cut. How many points of the strip must be compared with a given one if you go up the strip from the bottom?
3The idea
This is the divide-and-conquer closest pair algorithm. The points are sorted by x once, and the recursion returns its piece sorted by y, by merging the two halves. At the cut, select the points closer than d in x and compare each with the following ones in y while the difference in y is less than d: there are at most seven.
4Walkthrough
Everything is in integer squares: the distance to the cut is compared as (x − xm)² < d², the height difference as Δy² ≥ d². A squared distance goes up to 8·10¹⁸ (the ninth test) and fits in a signed 64-bit integer.
Why neighbours by x are not enough. A speed-up suggests itself: sort by x and compare each point with a few following ones. On random points this almost always finds the answer, but in the sixth test the points stand at nine heights in turn: neighbours by x are far apart in height, while the closest pair, points at the same height, is separated in x order by eight others. A window of eight does not see it. The strip ordered by y works differently: it looks at neighbours by height, and the seven-neighbour lemma guarantees they are few.
Coinciding points. In the second and eighth tests the answer is 0. The algorithm copes with this by itself: as soon as d = 0, the strips are empty, and the recursion ends quickly.
4+Solution
5Complexity
O(n log n): sorting and log n levels of recursion with linear combining. If the strip is sorted anew in each call, the result is O(n log² n), which also passes, but more slowly.
6Common mistakes
- A window of neighbours by x. It fails on the sixth test; see above.
- Square roots and floating point. Squared distances up to 8·10¹⁸ lose precision in a
double; compare integer squares. - 32-bit numbers. A coordinate difference of up to 2·10⁹ no longer fits in 32 signed bits, let alone its square.
- A strip from one half. Pairs inside the halves have been checked by the recursion, but the strip needs the points of both halves mixed together and ordered by y: otherwise pairs across the cut will not be found.