k-nearest neighbours labels a new point by asking its closest training points. Implement it for points on a plane.
What to build
A program that classifies query points with k-nearest neighbours.
Requirements
- For each query, take the k training points closest to it by straight-line distance; among points at equal distance, earlier training points come first.
- Predict the label that appears most often among those k points; on a tie, the alphabetically first of the tied labels.
- Print
X Y -> LABELfor each query, with X and Y exactly as given.
Input
Line 1: n and k. Then n lines X Y LABEL. Then a line with q, followed by q lines X Y.
Output
One line per query.
Constraints
1 ≤ k ≤ n ≤ 500; 1 ≤ q ≤ 100; labels are single words.
Example
Input:
6 3
1 1 red
2 1 red
1 2 red
6 6 blue
7 6 blue
6 7 blue
3
2 2
5 5
4 4
Output:
2 2 -> red
5 5 -> blue
4 4 -> red
Why it works
Points that are close in feature space tend to share a label, so a vote among the nearest k smooths out the odd mislabelled point while keeping the decision local.
Examples
6 3 1 1 red 2 1 red 1 2 red 6 6 blue 7 6 blue 6 7 blue 3 2 2 5 5 4 4
2 2 -> red 5 5 -> blue 4 4 -> red
2 1 0 0 a 10 0 b 3 3 0 7 0 5 0
3 0 -> a 7 0 -> b 5 0 -> a
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Squared distance (dx² + dy²) orders points the same way as distance and avoids square roots.
Hint 2
sorted() is stable: training points at the same distance keep their input order.
Hint 3
On a tie in the vote, take the alphabetically first of the tied labels.
Solution
Show one correct solution (try it yourself first)
n, k = map(int, input().split())
train = []
for _ in range(n):
x, y, label = input().split()
train.append((float(x), float(y), label))
q = int(input())
for _ in range(q):
sx, sy = input().split()
x, y = float(sx), float(sy)
near = sorted(train, key=lambda p: (p[0] - x) ** 2 + (p[1] - y) ** 2)[:k]
votes = {}
for _, _, label in near:
votes[label] = votes.get(label, 0) + 1
best = min(votes, key=lambda lab: (-votes[lab], lab))
print(f"{sx} {sy} -> {best}")