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}$.

제한

힌트