Squared-Distance Audit
A museum asks you to classify paintings by style on a simple 2D feature map. Your calculator’s square-root key is broken, so you must rank neighbors using squared Euclidean distance only: .

For each new painting, find the k
nearest known paintings by increasing (no sqrt). If two or more known paintings have exactly the same distance, prefer the one that appears earlier in the input.
Predict the style by majority vote among those k
. If the vote is tied, choose the earliest in the input.
The first line of the input contains a single integer n
representing the number of known paintings.
The next n
lines contain two floating-point numbers x y
followed by a style word such as modern
or classic
, describing one painting’s position and style.
The next line contains a single integer k
representing how many neighbors to use.
The next line contains a single integer q
representing the number of paintings to classify. The last q
lines each contain two floating-point numbers x y
for a new painting’s position.
The program should print one line per query: first, the predicted style, then the k
squared distances used, listed in neighbor order.
Input | Output |
---|---|
4 | classic 0.82 1.22 4.42 |
3 | modern 1 1 |
5 | modern 0.25 1.25 1.25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB