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:

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

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?