Implement Piecewise Linear Interpolation and Extrapolation

Given `n` points `(x_knots[i], y_knots[i])` in arbitrary order and a query `x_input`, implement piecewise linear interpolation without using an interpolation library: ```text linear_interpolate( n: int, x_knots: List[float], y_knots: List[float], x_input: float ) -> float ``` Sort the knots by `x`. If `x_input` lies between two adjacent knots, return the value on the line segment connecting them. If it lies outside the knot range, extrapolate using the nearest end segment. ### Constraints - `2 <= n <= 200_000` - `len(x_knots) == len(y_knots) == n` - Every `x_knots[i]`, `y_knots[i]`, and `x_input` is finite and has absolute value at most `10^6`. - All `x_knots` are distinct. After sorting, every adjacent pair differs by at least `10^-6`. - An answer within `1e-9` absolute or relative error is accepted. ### Clarifications - If `x_input` equals a knot exactly, return that knot's `y` value. - Left extrapolation uses the two smallest `x` values; right extrapolation uses the two largest. - The function handles one query, but the search should still be logarithmic after sorting. - The magnitude and separation bounds keep the slope, extrapolation product, and returned value finite in the IEEE 754 double precision used by all four console languages. ```hint Locate the bracketing segment After sorting paired knots, use binary search for the first knot whose x-coordinate is not less than the query, then clamp the segment index at the two ends. ``` ### Examples ```text Input: n = 3, x_knots = [2, 0, 1], y_knots = [4, 0, 1], x_input = 1.5 Output: 2.5 Input: n = 3, x_knots = [2, 0, 1], y_knots = [4, 0, 1], x_input = -1 Output: -1 ``` ### Evaluation Focus - Preservation of each `(x, y)` pair during sorting. - Correct segment choice at knots and outside the range. - The linear interpolation formula and floating-point behavior. - (O(n\log n)) preprocessing and (O(\log n)) lookup. ### Extension How would you preprocess once to answer one million query values efficiently?