KNN Regression: How Many Stars?

A tiny streaming app wants a quick guess for a brand-new movie’s rating. Picture every known movie placed on a simple 2D map: movies that sit closer together feel more alike. To guess the new movie’s stars, you can look at the k closest known movies on this map (by straight-line distance), average their ratings, and use that number.

If some candidates are exactly the same distance when ranking neighbors, break the tie by trusting the one that appears earlier in the input.

The first line of the input contains a single integer n representing the number of known movies. The next n lines contain two floating-point numbers x y followed by a floating-point number r, describing that movie’s position and its rating in stars.

The next line contains a single integer k.

The next line contains a single integer q representing the number of new movies to estimate. The last q lines each contain two floating-point numbers x y for a new movie’s position.

For each new movie, print the predicted rating.