Line of Best Fit

Finding a line that best fits a set of data points in the plane is one of the fundamental problems in statistics and numerical analysis.

You are given a set $P$ of $n$ points in the plane, $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$. For a line $L$ defined by the linear equation $y = ax + b$, the error of $L$ with respect to $P$ is defined as the sum of the squared vertical distances from the points of $P$ to the line:

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

The least squares method finds the line $L$ that minimizes this error. Write a program that, for a given set of points $P$, computes the coefficients $a$ and $b$ of the line $L$ that minimizes the error.

Figure 1. An example of a set of points and its line of best fit.

The first line contains the number of points $n$ ($1 \le n \le 1{,}000$). Each of the next $n$ lines contains two integers $x_i$ and $y_i$, the coordinates of a point, separated by a space ($|x_i| \le 10^6$, $|y_i| \le 10^6$). It is guaranteed that the $x$-coordinates are not all identical, so the line of best fit is uniquely determined.

Print the value of $a$ on the first line and the value of $b$ on the second line. Both values must be rounded to three decimal places.