28164번 - Optimal Quadratic Function 스페셜 저지다국어

Two variables $x$ and $y$ are dependent to each other with the relation $y=f(x)$ where $f$ is a quadratic function: $f(x) = a x^2 + b x + c$ with some real numbers $a$, $b$, and $c$. However, the function $f$ is unknown and you want to figure out its best estimation.

For that purpose, you have obtained $N$ observed $y$-values $y_1, y_2, \ldots, y_N$ for $x$-values $x_1, x_2, \ldots, x_N$, respectively, by experiments. The observed values $y_1, y_2, \ldots, y_N$ contain some errors from several sources, so it is unlikely that all of them are exact function values for a certain quadratic function. Therefore, you need to find an optimal estimation of the function $f$ that minimizes the error.

For any quadratic function $f$, the error of a data pair $(x_i, y_i)$ is defined to be $(y_i-f(x_i))^2$, and the error of $f$ is defined to be the maximum of these errors over all the $N$ data pairs. Write a program that, given the $N$ observed data pairs, finds out an optimal estimation of function $f$ that minimizes the error and prints out the error value.

The first line contains an integer $T$, the number of test cases ($1 \le T \le 100\,000$). The test cases follow.

The first line of each test case contains an integer $N$, the number of observed data pairs ($1 \le N \le 100\,000$).

Each of the next $N$ lines contains two integers $x_i$ and $y_i$, the $i$-th data pair ($-10^6 \le x_i, y_i \le 10^6$).

The sum of $N$ over all test cases does not exceed $200\,000$.

For each test case, print a line with a real number: the minimum possible error value.

The answer will be considered correct if its absolute or relative error is within $10^{-6}$.