Compute Piecewise Linear Interpolation

You are given an unsorted list of distinct 2D points (x_i, y_i). When the points are sorted by x_i, connecting adjacent points forms a polyline.

Given a query value x, return the corresponding y value on this polyline:

• If x exactly matches an existing point's x-coordinate, return that point's y-coordinate.
• If x lies between two adjacent points, use linear interpolation.
• If x is smaller than the minimum x-coordinate, extrapolate using the first two points after sorting.
• If x is larger than the maximum x-coordinate, extrapolate using the last two points after sorting.

Design an efficient algorithm. You may assume there are at least two points and all x-coordinates are distinct.

Example:

points = [(0, 0), (10, 20), (20, 10)]
x = 5
output = 10

Explanation: x = 5 lies halfway between (0, 0) and (10, 20), so the interpolated y-value is 10.