Classify points with k-nearest neighbours and the Euclidean distance. If two training points are equally far, the one listed first counts as nearer.
Input
The first line has n and k (1 ≤ k ≤ n ≤ 200, k odd). Each of the next n lines has a training point x y label, where there are exactly two different labels in the whole set. Then a line with q (1 ≤ q ≤ 50) and q query lines x y.
Output
The predicted label for each query, one per line.
Examples
Example 1 · Input
6 3 150 7.0 apple 170 7.5 apple 140 6.8 apple 130 7.2 orange 120 6.5 orange 125 7.0 orange 2 135 7.1 160 7
Expected output
orange apple
Example 2 · Input
4 1 0 0 a 10 10 b 0 10 a 10 0 b 3 1 1 9 8 5 5
Expected output
a b a
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each query, sort the training points by Euclidean distance; Python's sort keeps the input order for ties.
Hint 2
Take the first k and count the labels.
Hint 3
k is odd and there are two labels, so the vote cannot tie.
Solution
Show one correct solution (try it yourself first)
n, k = map(int, input().split())
training = []
for _ in range(n):
x, y, label = input().split()
training.append((float(x), float(y), label))
for _ in range(int(input())):
qx, qy = map(float, input().split())
ranked = sorted(training, key=lambda t: (t[0] - qx) ** 2 + (t[1] - qy) ** 2)
votes = {}
for t in ranked[:k]:
votes[t[2]] = votes.get(t[2], 0) + 1
print(max(votes, key=votes.get))