Description

Given $n$ quadratic functions $f_1(x), f_2(x), \dots, f_n(x)$ (each of the form $ax^2+bx+c$), let $F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\}$. Find the minimum value of $F(x)$ on the interval $[0, 1000]$.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains a positive integer $n$. Then $n$ lines follow, each with $3$ integers $a, b, c$ representing the three coefficients of a quadratic function. Note that a quadratic function may degenerate into a linear function.

Output Format

For each test case, output one line with the minimum value of $F(x)$ on the interval $[0, 1000]$. The answer should be rounded to $4$ decimal places.

2
1
2 0 0
2
2 0 0
2 -4 2

0.0000
0.5000

Hint

For $50\%$ of the testdata, $n \le 100$.

For $100\%$ of the testdata, $T < 10$, $n \le 10^4$, $0 \le a \le 100$, $|b| \le 5 \times 10^3$, $|c| \le 5 \times 10^3$.

Translated by ChatGPT 5