The density threshold

clustering points sorting binary search precomputation geodata

Before running DBSCAN, a radius ε has to be chosen. An analyst wants to turn it back and forth and see at once how many points will be cores at that radius. And sometimes asks the other way round: at what smallest radius will at least c points become cores, for example four points out of five.

Given n points of the plane and a threshold minPts. At radius ε the neighbours of a point are all points at a distance of at most ε from it, including itself (points with the same coordinates are different points). A point is a core if it has at least minPts neighbours. Answer queries of two kinds:

1 e: how many cores there are at ε = e;
2 c: the smallest integer ε at which there are at least c cores.

Tests three to five are real epicentres of earthquakes of magnitude 5 and above from the USGS catalogue: an arc of islands in the north-west Pacific for 2018–2021 and for all of 2015–2025, then the south-west Pacific for 2015–2018. Coordinates are kilometres on a flat map of the region.

Input

The first line holds n and minPts (1 ≤ minPts ≤ n ≤ 2000). Then n lines with integer coordinates x, y (at most 10⁶ in absolute value). Then the number of queries q (1 ≤ q ≤ 10⁵) and q lines with queries: in a query of the first kind 0 ≤ e ≤ 3·10⁶, of the second 1 ≤ c ≤ n.

Output

For each query, a number on a separate line.

Examples

Example 1

Input

Output

Example 2

Input

Output

Limits

Time · Python: 9500 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 12 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

Recounting neighbours for every query is up to 10⁵ times 4·10⁶ distances. What changes for a single point as ε grows?

2Hint 2

If a point is a core at some ε, it is a core at any larger one too. So each point has its own threshold: the ε from which it becomes a core. What does it equal?

3Hint 3

A core needs minPts neighbours, and one of them is the point itself. How many other points must fall into the circle?

4The idea

A point's threshold is the distance to its (minPts − 1)-th nearest neighbour among the other points (zero for minPts = 1). This is the “core distance” from which the sorted graph for choosing ε is built in the article. Compute the threshold of each point and sort: the number of cores at ε is how many thresholds are at most ε (binary search), and the smallest ε for c cores is the c-th smallest threshold.

5Walkthrough

For each point compute the squared distances to all points, including itself, and sort: position 0 holds the point itself (or its twin, also 0), and position minPts − 1 the threshold sought. Squared distances are convenient: everything stays in integers, and the comparison “threshold ≤ ε” becomes “squared threshold ≤ ε²”.

A query of the first kind is bisect_right over the sorted squared thresholds with the value e². The second kind needs the c-th smallest squared threshold D, and the answer is the smallest integer ε with ε² ≥ D: that is ⌈√D⌉. Most precise is to take the integer root (math.isqrt) and add one if it is not exact. Go's standard library has no integer root: you can take math.Sqrt and correct the result in integers until r² is exactly in place.

On the arc of islands over eleven years (913 earthquakes, minPts = 10), at ε = 100 km 854 points are cores, and 58 km is enough for 80 % of the points, 731 of them, to become cores. Over eleven years many shocks have accumulated at every place of the arc, and the density threshold is passed at a small radius already.

5+Solution

6Complexity

O(n² log n) for the thresholds (sorting the distances for each point; O(n²) is also possible by selecting the k-th element) and O(n log n + q log n) for sorting the thresholds and the answers. For large n the thresholds are computed with a grid or a k-d tree: only the minPts − 1 nearest neighbours are needed, not all the distances.

7Common mistakes

A neighbour one too far. If you take the distance to the minPts-th other neighbour, forgetting that the point counts itself, every threshold comes out one neighbour stricter. This is how the k-distance graph of the original paper reads when taken literally, with k = minPts; the correction “k = minPts − 1” was later spelled out by Schubert and co-authors. The first sample already catches it.
Recounting for every query. Correct, but 10⁵ queries of 4·10⁶ distances will not fit in any time.
Strictly less instead of “at most”. A point at exactly ε is a neighbour, so a threshold equal to ε passes: you need bisect_right, not bisect_left. In the first sample at ε = 5 the threshold of the point (3, 4) is exactly 5.

Algorithms behind it

ML Algorithm DBSCAN Gathers dense regions of points of any shape into clusters and marks lone points as noise. O(n·Q + Σ|N(p)|) 2 problems SRT Algorithm Binary search Finds the “no → yes” boundary in ordered data in log₂ n checks. O(log n) 2 problems