Pairs closer than r
A seismologist looks in a catalogue for earthquakes that happened almost in the same place: aftershocks, swarms, duplicate records. To begin with, they want to know how many pairs of epicentres lie at most r apart. Given points on a plane and a number r, count the pairs of points at a distance of at most r.
The second test is all earthquakes of magnitude 5 and above for 2015–2025 from the USGS catalogue, the third the 45,227 cities of the world with 10 thousand people or more from the GeoNames gazetteer; both as points (longitude, latitude) in thousandths of a degree, ignoring the fact that the Earth is round.
Input
The first line holds the number of points n (1 ≤ n ≤ 100,000) and the distance r (1 ≤ r ≤ 10⁹). Then n lines with coordinates x y, integers, |x|, |y| ≤ 10⁹. Points may coincide. The answer is guaranteed to be at most 10⁶.
Output
The number of unordered pairs of points at a distance of at most r.
Examples
Example 1
6 5 0 0 3 4 6 8 10 0 3 4 20 20
5
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 9 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
All pairs means up to 5·10⁹ checks. But a pair at a distance of at most r cannot be just anywhere: the points are close in both x and y. How do you arrange the points so that for each you can quickly find those nearby?
2Hint 2
Put the points into grid squares with side r. Where can a point at most r from a given one lie? And how do you avoid counting the same pair twice?
3The idea
A point's square is (⌊x/r⌋, ⌊y/r⌋). Two points at most r apart differ by at most r in each coordinate, so their squares are the same or neighbouring, diagonal neighbours included. Keep the squares in a hash table: square → its points. Look at each pair of squares once: a square with itself (pairs inside) and with four “forward” neighbours, top right, right, bottom right and top. The other four neighbours are someone else's “forward” ones, and their pairs are counted there.
4Walkthrough
Inside a square go through pairs, with neighbours through all combinations, and check (Δx)² + (Δy)² ≤ r² for each in integers. For negative coordinates the square number is conveniently computed with rounding down, // in Python; in Go division rounds towards zero, and the square at zero would come out twice as wide. That would not spoil the answer, as all that matters is that no square is narrower than r, but there would be more checks.
This is the same grid as in the closest pair search, only the square's side is given in advance, and nothing needs rebuilding.
4+Solution
5Complexity
Placing the points is O(n) on average. The checks are as many as the pairs of points in neighbouring squares. Pairs in neighbouring squares are less than 2√2·r apart, and on data without special clusters there are only a few times more of them than pairs closer than r: O(n + answer). On points with very many pairs just over r apart the work is larger, which is why the statement bounds the answer.
6Common mistakes
- All pairs. Correct, but on a hundred thousand points that is five billion checks.
- All eight neighbours without “forward”. If each square is checked against all eight neighbours, every pair from different squares is counted twice.
- Squares narrower than r. If a square's side is less than r, a nearby point can be one square further away rather than in a neighbouring one, and such pairs are lost.
- A strict inequality. Pairs at a distance of at most r are needed; in the first sample four pairs are exactly 5 apart.
Algorithms behind it
O(n log n)
2 problems
DS
Data structure
Hash table
Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell.
O(1) on average
2 problems