Piecewise Linear Interpolation and Extrapolation for Polyline

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) Example Input 3 4 2 2 0 0 1 1 -1 0.5 2 3 Output -1.0000000000 0.5000000000 2.0000000000 3.0000000000