Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.
KNN
K Nearest Neighbour (KNN) is a famous classification method.
It finds the K-nearest neighbors according to given metric
distance. Then, it decides the class of current object
according to majority of the nearest neighbors.
Assuming K=4, the right image shows the four close
neighbors in a circle (3 red dots and 1 green plus).
Since the majority of the neighbors are red dots,
then the test sample is assigned to the class of
red dots.
Question:
Write a program that is going to classify
m points according to dataset given. Assume that a point
is closer if its Euclidean distance is smaller. If
Euclidean distances are the same then, the node which
is alphabetically smaller is closer.
Input specification
First, you will be given two integers (n and K)
where n is between 0 and 5000 and K is between 1
and 100. Then, in the following n lines, you will
be given the information for n objects where every
line contains the following information:
- x, y, z coordinates of the object where the
coordinates are integers between -20000 and 20000
- the class of the object: a string not more than 10 chars
Then, on the following line, you are given another integer (m):
the number of querying objects. And, in the following m
lines, you will be given 3D coordinates of m objects where
m is between 1 and 100. There are not more than 100
classes.
Output specification
Show the classes of m objects in m lines. If there are
many classes having the same number of majority votes,
assign the class which is alphabetically greater. e.g.
red is alphabetically greater than blue.
Sample Input I
9 4
1 3 0 red
1 2 0 red
2 2 0 red
2 5 0 red
1 5 0 red
3 4 0 blue
1 5 0 blue
2 5 0 blue
3 5 0 blue
1
3 3 0
|
Sample Output I
red
|
Для отправки решений необходимо выполнить вход.
|