Linear Interpolator with Extrapolation

You are given n knot points in a 2D coordinate system, where knots[i] = [x_i, y_i]. All x-coordinates are distinct, but the points are given in no particular order.

After sorting the knots by x-coordinate, connecting each consecutive pair of knots with a straight line segment defines a piecewise linear function L(x) — a linear interpolator — on the interval [x_min, x_max], where x_min and x_max are the smallest and largest knot x-coordinates.

Outside that interval, L(x) is defined by linear extrapolation:

• For x < x_min, extend the straight line that passes through the two leftmost knots.
• For x > x_max, extend the straight line that passes through the two rightmost knots.

Write a function:

interpolate(knots, queries) -> answers

that returns an array answers of the same length as queries, where answers[j] = L(queries[j]).

Example 1

Input: knots = [[0, 0], [10, 10], [20, 0]]
 queries = [5, 10, 15]
Output: [5.0, 10.0, 5.0]

Explanation: The segment from (0, 0) to (10, 10) has slope 1, so L(5) = 5. x = 10 is exactly a knot, so L(10) = 10. The segment from (10, 10) to (20, 0) has slope -1, so L(15) = 5.

Example 2

Input: knots = [[10, 10], [0, 0], [20, 0]]
 queries = [-5, 25]
Output: [-5.0, -5.0]

Explanation: The knots are unsorted; after sorting by x they are (0, 0), (10, 10), (20, 0). For x = -5 < x_min = 0, extrapolate the line through the two leftmost knots (0, 0) and (10, 10) (slope 1): L(-5) = -5. For x = 25 > x_max = 20, extrapolate the line through the two rightmost knots (10, 10) and (20, 0) (slope -1): L(25) = 0 + (-1) * (25 - 20) = -5.

Constraints

• 2 <= n <= 100,000
• 1 <= len(queries) <= 100,000
• -10^9 <= x_i, y_i, queries[j] <= 10^9, real numbers with at most 6 digits after the decimal point
• All x_i are distinct
• A query may fall exactly on a knot, between knots, or outside the knot range
• Answers are accepted within an absolute or relative error of 10^-6

Your solution should sort the knots once and locate each query's segment efficiently — an O((n + q) log n) approach is expected, where q is the number of queries.