Piecewise Linear Interpolation and Extrapolation

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Original prompt

Problem: Piecewise Linear Interpolation and Extrapolation for a Polyline

You are given a set of 2D points [(x1,y1), (x2,y2), ..., (xn,yn)]. After sorting points by increasing x, connect consecutive points with straight line segments to form a polyline.

For each query xq, output the corresponding yq on this polyline:

If xq lies between two adjacent points xi <= xq <= xi+1, perform linear interpolation on that segment. If xq < x1, extrapolate by extending the leftmost segment ((x1,y1)–(x2,y2)). If xq > xn, extrapolate by extending the rightmost segment ((x_{n-1},y_{n-1})–(xn,yn)). If xq equals some xi, return yi exactly. Input (stdin) First line: two integers n q (#points, #queries) Next n lines: two real numbers x y Next q lines: one real number xq Output (stdout)

For each query print one line yq (floating-point; 1e-6 error tolerated).

Constraints

2 <= n <= 2e5 1 <= q <= 2e5 Points may be unsorted; sort them. After sorting, all x are strictly increasing. Target overall complexity: O((n+q) log n).

Formula

Given (xa,ya) and (xb,yb) (xa != xb):

y(x) = ya + (yb - ya) * (x - xa) / (xb - xa)

Complete solvePiecewiseLinearInterpolation. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.