#6. 「一本通 1.2 例 3」曲线

「一本通 1.2 例 3」曲线

题目描述

明明做作业的时候遇到了 nn 个二次函数 Si(x)=ax2+bx+cS_i(x)= ax^2 + bx + c,他突发奇想设计了一个新的函数 F(x)=max{Si(x)},i=1nF(x) = \max\{S_i(x)\}, i = 1\ldots n

明明现在想求这个函数在 [0,1000][0,1000] 的最小值,要求精确到小数点后四位,四舍五入。

输入格式

输入包含 TT 组数据,每组第一行一个整数 nn

接下来 nn 行,每行 33 个整数 aa, bb, cc ,用来表示每个二次函数的 33 个系数。注意:二次函数有可能退化成一次。

输出格式

每组数据输出一行,表示新函数 F(x)F(x) 的在区间 [0,1000][0,1000] 上的最小值。精确到小数点后四位,四舍五入。

样例

2
1
2 0 0
2
2 0 0
2 -4 2
0.0000
0.5000

数据范围与提示

对于 50%50\% 的数据,1n1001 \leq n \leq 100

对于 100%100\% 的数据,1T101 \leq T \leq 10, 1n1051 \leq n \leq 10^5, 0a1000 \leq a \leq 100, 0b50000 \leq |b| \leq 5000, 0c50000 \leq |c| \leq 5000