Piecewise Linear Interpolation
MediumArrays ยท Two Sigma
points holds [x, y] readings in no particular order, with distinct x values. The curve through them is made of straight lines joining readings that are consecutive by x. Left of the smallest x the curve continues the first line, and right of the largest x it continues the last line.
Return a list with the curve's y value for each x in queries, in the same order.
Example 1
- Input:
- points = [[4, 5], [0, 1], [2, 7]], queries = [1, 3, 5]
- Output:
- [4.0, 6.0, 4.0]
- Explanation
- Sorted by x the readings are (0, 1), (2, 7), (4, 5). At x = 5 the last line, which falls 1 per unit, continues to 4.
Example 2
- Input:
- points = [[1, 3], [5, 3]], queries = [-2, 9]
- Output:
- [3.0, 3.0]
Example 3
- Input:
- points = [[0, 0], [1, 1], [3, -1]], queries = [0, 1, 2, 4]
- Output:
- [0.0, 1.0, 0.0, -2.0]
Constraints
2 <= points.length <= 10^50 <= queries.length <= 10^5-10^4 <= x, y <= 10^4for every reading, and each query- Answers within
1e-6of the true value are accepted