THE ROCHESTER NORMAL EQUATION

Difficulty: Medium Tags: Classical ML, Linear Regression, Numerical Methods

Story

An operations analyst fits a simple linear model from delivery distance and observed time. The implementation must include an intercept and use the closed-form one-feature least-squares formula, even when the distance values are not centered.

The Math

For pairs (x_i, y_i), slope and intercept are:

w1 = sum_i((x_i - x_mean)*(y_i - y_mean)) / sum_i((x_i - x_mean)^2)
w0 = y_mean - w1 * x_mean

If all x_i are equal, w1 = 0 and w0 = y_mean. Predict at each query q using y_hat = w0 + w1*q.

Input Format

points (list of (x, y) pairs), queries (list of x values).

Output Format

(w0, w1, predictions), each to 6 decimal places.

Constraints

• 1 <= n, m <= 10^5, |x_i|, |y_i| <= 10^6.
• Time limit: 1.0 second.

Example

Input

points = [(1, 5), (2, 7), (3, 9)], queries = [4, 5]

Output

(3.000000, 2.000000, [11.000000, 13.000000])

Explanation: The data exactly follows y = 3 + 2x.