Predict with a best-fit line

Fit the least-squares line to some data, then use it to predict y for new values of x.

What to build

A program that fits y = a + b·x and prints predictions.

Requirements

  • Print slope B and intercept A, each to 2 decimal places.
  • For each query x, in order, print predict X: Y, where X is the query exactly as given and Y has 2 decimal places.

Input

The first line is n; each of the next n lines has x and y; the last line has one or more query x values.

Output

Two lines, then one line per query.

Constraints

2 ≤ n ≤ 1000; the x values are not all equal; 1 to 20 queries.

Example

Input:

6
1 52
2 55
3 61
4 64
5 70
6 73
7 0

Output:

slope 4.37
intercept 47.20
predict 7: 77.80
predict 0: 47.20

Why it works

The slope b = sxy ÷ sxx minimises the sum of squared vertical errors, and a = ȳ − b·x̄ makes the line pass through the point of means.

Examples

Example 1 · Input
6
1 52
2 55
3 61
4 64
5 70
6 73
7 0
Expected output
slope 4.37
intercept 47.20
predict 7: 77.80
predict 0: 47.20
Example 2 · Input
3
0 1
1 3
2 5
3 10
Expected output
slope 2.00
intercept 1.00
predict 3: 7.00
predict 10: 21.00

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

b = sxy ÷ sxx and a = ȳ − b·x̄.

Hint 2

Keep each query x as the text you read, so it prints exactly as given.

Solution

Show one correct solution (try it yourself first)
n = int(input())
pts = [tuple(map(float, input().split())) for _ in range(n)]
mx = sum(x for x, _ in pts) / n
my = sum(y for _, y in pts) / n
sxy = sum((x - mx) * (y - my) for x, y in pts)
sxx = sum((x - mx) ** 2 for x, _ in pts)
b = sxy / sxx
a = my - b * mx
print(f"slope {b:.2f}")
print(f"intercept {a:.2f}")
for q in input().split():
    print(f"predict {q}: {a + b * float(q):.2f}")

Lesson: Correlation and regression →