최소제곱 직선

평면 위의 데이터 점들에 가장 잘 맞는 직선(line of best fit)을 찾는 것은 통계학과 수치해석의 기본 문제 중 하나이다.

평면 위에 $n$개의 점 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$으로 이루어진 집합 $P$가 주어진다. 직선 $L$이 일차방정식 $y = ax + b$로 정의될 때, $P$에 대한 $L$의 오차(error)를 각 점에서 직선까지의 세로 거리를 제곱하여 모두 더한 값으로 정의한다.

$\text{Error}(L, P) = \sum_{i=1}^{n} (y_i - a x_i - b)^2$

최소제곱법(least squares)은 이 오차를 최소로 만드는 직선 $L$을 찾는 방법이다. 주어진 점 집합 $P$에 대하여 오차를 최소화하는 직선 $L$의 계수 $a$와 $b$를 구하는 프로그램을 작성하시오.

그림 1. 점들과 그에 대한 최소제곱 직선의 예.

첫째 줄에 점의 개수 $n$이 주어진다 ($1 \le n \le 1{,}000$). 다음 $n$개의 줄에는 각 점의 좌표 $x_i$와 $y_i$가 공백으로 구분되어 주어진다 ($|x_i| \le 10^6$, $|y_i| \le 10^6$). 모든 점의 $x$좌표가 같지는 않음이 보장되며, 따라서 최소제곱 직선은 유일하게 결정된다.

첫째 줄에 $a$의 값을, 둘째 줄에 $b$의 값을 출력한다. 두 값 모두 소수점 아래 셋째 자리까지 반올림하여 출력한다.