A district by its neighbours
For n crossroads of a city it is known which district they belong to. For q new points the district has to be named by the vote of the k nearest neighbours, as in the article and with all its rules, so that the answer is unique:
- the distance is the ordinary straight-line one;
- neighbours are ordered by distance, and at equal distance by the crossroads’ number in the input (earlier means nearer); the first k vote;
- the district with the most votes wins; if there are several such districts, the one whose crossroads comes earliest in the list of neighbours.
One of the tests is the real crossroads of central Almaty with districts by the borders from OpenStreetMap: two thousand are known, and a thousand others are asked about.
Input
The first line holds the numbers n and k (1 ≤ k ≤ n ≤ 2000). Each of the following n lines holds integers x, y (|x|, |y| ≤ 10⁶) and a district number c (1 ≤ c ≤ 20). Then the number of questions q (1 ≤ q ≤ 1000) and q lines with the integer coordinates of the points.
Output
For each question, the district number on a separate line.
Examples
Example 1
7 4 60 80 2 90 -120 1 -108 144 1 -132 -176 2 0 260 3 180 240 3 -192 256 3 3 0 0 500 500 -100 0
2 3 1
Example 2
25 2 0 0 1 100 0 2 200 0 3 300 0 1 400 0 2 0 100 3 100 100 1 200 100 2 300 100 3 400 100 1 0 200 2 100 200 3 200 200 1 300 200 2 400 200 3 0 300 1 100 300 2 200 300 3 300 300 1 400 300 2 0 400 3 100 400 1 200 400 2 300 400 3 400 400 1 5 50 50 200 200 250 150 0 0 450 450
1 1 2 1 1
Limits
- Time · Python
- 8000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 8 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
There is no need to take a root: the order of the neighbours by squared distance is the same, and the squares of integer coordinates are integers, so the comparisons are exact.
2Hint 2
Look at the first example: at k = 4 the Almaly (1) and Medeu (2) districts have two votes each. Which will your program name, and why? The usual “most common” in libraries picks, on a tie, the first counted, not the nearest.
3The idea
This is the k nearest neighbours method in its pure form. All the difficulty is in the rules: neighbours are sorted by the pair (squared distance, number), and on a tie in votes you go through the neighbours from nearest to farthest and take the first district that has the maximum of votes.
4Walkthrough
For each question compute the pairs (d², number) for all known crossroads and choose the k smallest: in Python heapq.nsmallest, in Go a short ordered list into which a new pair is inserted only if it is smaller than the last. Comparing pairs orders equal distances by number by itself. Then count the votes and go through the neighbours once more in the same order: the first whose district got the maximum is the answer.
On the Almaty test the vote of five neighbours goes wrong only at crossroads near the district borders, as in the article’s scene.
4+Solution
5Complexity
O(n log k) per question, O(q·n log k) in all: up to two million distances.
6Common mistakes
- A tie in favour of the smaller number.
Counter.most_commonandmaxover a dictionary pick, on a tie, the district met first in the count, not the nearest. The first example catches this. - An unstable sort of the neighbours. If you sort only by distance, equidistant crossroads (the second test has many, a grid) can come in any order, and with k at the boundary the wrong ones vote.