Imagine you are the Process Engineer on the floor of a pencil-making factory. Your job involves looking after the machine which cuts the pencils to a specific length. The machine is quite accurate, but a number of factors cause random variations in length from pencil to pencil - for example, sometimes a pencil sits in the machine a little differently than the one before it.
Additionally there are some factors affecting accuracy at larger time scales - for example after cutting many times the fixture holding the pencil being cut may get shifted.
Every minute or so, a technician takes a pencil produced by the machine and measures the deviation from the target length, with positive values indicating an oversized pencil and negative values indicating an undersized pencil.
At the end of the shift, you are given all of this measurement data and asked to create a trendline through the noisy data to help make sense of how the machine should be adjusted.
Specifically, you are to provide the m and b values of the trendline in the format y = m*x + b.
A trendline is fitted to a set of noisy data to help make predictions about that data. How well a given line fits to a set of data can be scored by calculating it's $R^2$ value, also called the goodness-of-fit value or more formally the coefficient of determination.
$$ \huge R^2 = 1 - \frac{\sum (y_i - \hat{y}_i)^2}{\sum (y_i - \bar{y})^2} $$
If it's not clear, the equation above takes the 'sum of the squares', not the 'square of the sum'.
Where
- $y_i$ is actual measured value
- $\hat{y}_i$ is calculated value from the trendline equation
- $\bar{y}$ is mean average measured
yvalue.
Greater values of $R^2$ indicate better fits than lower values.
A $R^2$ value of 1 indicates a perfect fit.
The above trendline in blue through the dataset in red is the best possible fit to maximize the $R^2$ value.
Problem Statement
You will be given a dataset of n coordinate pairs of (x, y) values.
Calculate the m and b values corresponding to the trendline in format y = m*x + b which yields the maximum possible $R^2$ value.
Input Data
First line will be n, the quantity of datapoints.
n lines will then follow, each with two values x y represending a coordinate pair.
Answer
Should consist of 3 space-separated values m, b, and $R^2$.
Error should be less than 1e-6.
Example
input data:
20
1 176
31 106
63 147
94 156
123 159
157 151
185 134
214 207
246 140
276 131
306 120
336 42
366 112
397 114
430 99
462 78
493 7
521 63
548 115
581 115
answer:
-0.160272 165.319300 0.392572