A district-heating pipe has n temperature sensors; sensor i sits at the whole-number position positions[i] (metres from the plant) and reads temps[i]. Several sensors can share a position, where old and new ones were fitted side by side. An inspector wants a temperature estimate at many points along the pipe.
Write knn_line(positions, temps, queries, k) that returns a list with one float per query: the mean reading of the query's k neighbours. The neighbours of a query q are the first k sensors when all sensors are ordered by abs(positions[i] - q), nearest first, with equal distances ordered by sensor index i (smaller first). If k > n, all sensors are neighbours.
The setup provides pipe_sensors(n, seed, length=10**6), which returns (positions, temps), and probe_points(m, seed, length=10**6), which returns m inspection points.
Examples
Input: positions = [0, 10, 10, 20, 30], temps = [50, 40, 44, 30, 20]
queries = [10, 15, 25], k = 3
Output: [44.666666666666664, 38.0, 30.0]
Explanation: for 10, sensors 1 and 2 are at distance 0, then sensors 0 and 3 are both 10 away
and the smaller index, 0, is taken: (40 + 44 + 50) / 3. For 15, sensors 1, 2 and 3 are all 5
away. For 25, sensors 3 and 4 are 5 away, then sensors 1 and 2 are 15 away: sensor 1.
Input: positions = [7, 3, 5, 5, 3], temps = [1, 2, 3, 4, 5], queries = [4], k = 3
Output: [3.0]
Explanation: four sensors are 1 away, two on each side; the three smallest indices are 1, 2, 3.
Constraints
1 <= n <= 10**5,0 <= len(queries) <= 10**4,1 <= k <= 50- positions, readings and queries are whole numbers between
0and10**6; floats are compared with a tolerance of1e-6 - each test must finish in well under a second in your browser: comparing every query with every sensor (up to 10⁹ distances) is far too slow
Goals
- Find the k nearest neighbours of many queries without scanning the whole training set each time
- Keep an exact tie-break when neighbours are equally far on both sides of a query
- Sort once, then answer each query in time that depends on k rather than on n