26108번 - Linear Regression 스페셜 저지다국어

Chansu is a graduate student at University of ICPC, working in a laboratory for his master’s degree. His research theme is to reveal a relation between the obesity and the yearly income of individuals in a certain group $G$.

Chansu collected data of the form $(x_i, y_i)$ from $n$ persons in $G$, where $x_i$ and $y_i$ denote the obesity index and the yearly income of the $i$-th person, and made an apparent hypothesis:

There is a linear dependency between the obesity and the yearly income of individuals in group $G$.

To prove his hypothesis, Chansu tried to find an optimal linear function $f^*(x)$ with real coefficients such that the error with respect to the collected data is minimized. More specifically, the error of $f$ with respect to the data is defined to be the maximum of $|y_i - f(x_i)|$ over all $i = 1, \dots , n$.

However, the result was disappointing because the error of the optimal function $f^*(x)$ was unexpectedly big. This means that his hypothesis cannot be proven in this way.

Chansu tried to figure out the reason of the big errors. One day, he plotted the data $(x_i, y_i)$ as points on the coordinated plane and realized that there are a small number $k$ of points that are unusually far from the others, so the error of the optimal function can be drastically reduced after removing them.

You, as a friend of Chansu, would love to help Chansu. Write a program that finds an optimal linear function minimizing the error after removing some $k$ values from the given data $\{(x_1, y_1), \dots , (x_n, y_n)\}$ and prints out the error value, when the number $k$ is given as part of input.

Your program is to read from standard input. The input starts with a line containing two integers, $n$ and $k$ ($1 ≤ n ≤ 50\,000$, $0 ≤ k ≤ \min{\{\frac{n}{2}, 300\}}$), where 𝑛𝑛 is the number of collected data values. In each of the following $n$ lines, each data value $(x_i, y_i)$ is given by two integers $x_i$ and $y_i$ ($-10^9 ≤ x_i, y_i ≤ 10^9$) for $i = 1, \dots , n$. You can assume that no three of them are collinear when plotting them in the coordinated plane.

Your program is to write to standard output. Print exactly one line. The line should contain a real number $z$ representing the minimum possible error of a linear function with respect to the data after removing some $k$ values. Your output $z$ should be in the format that consists of its integer part, a decimal point, and its fractional part, and will be decided to be “correct” if it holds that $a - 10^{-6} < z < a + 10^{-6}$, where $a$ denotes the exact answer.