Trail Guide: One-Neighbor After Fair Scaling

Your hiking app suggests routes using KNN. Each route is described by two features: slope in degrees and altitude in meters. Altitude numbers are much larger, so without scaling, they dominate distance, and KNN makes unfair choices. To fix this, you decide to scale both features first, then classify.

You are asked to read some preexisting data with labels, and then classify new rows. Compute the per-column minimum and maximum using the preexisting data only, scale both the preexisting rows and the new rows to the range [0,1], then predict each new row’s label using 1-NN in the scaled space. If a column in the preexisting data is flat (all values are equal), treat its scaled value as 0 everywhere. If several preexisting rows are tied for the smallest distance, pick the label of the row that appears earliest in the preexisting data.

The first line of the input contains two integers n and d representing how many labeled rows you have and how many features there are. In this story d = 2 - slope and altitude. Each of the next n lines contains d floating-point numbers followed by a label with no spaces.

The next line contains a single integer q representing how many new rows you want to classify. Each of the next q lines contains d floating-point numbers: slope and altitude, to classify using the scaling computed from the preexisting data.

The program should print q lines, each with the predicted label for the corresponding new row.