Problem1013--「一本通 1.2 例 3」曲线

1013: 「一本通 1.2 例 3」曲线

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 3  Solved: 2
Submit Status Web Board

Creator:

Description

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

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


Input

输入包含 TTT 组数据,每组第一行一个整数 nnn

接下来 nnn 行,每行 333 个整数 aaa, bbb, ccc ,用来表示每个二次函数的 333 个系数。注意:二次函数有可能退化成一次。


Output

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


Sample Input

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

Sample Output

0.0000
0.5000

HINT

对于 50%50\%50% 的数据,1≤n≤1001 \leq n \leq 1001n100

对于 100%100\%100% 的数据,1≤T≤101 \leq T \leq 101T10, 1≤n≤1051 \leq n \leq 10^51n105, 0≤a≤1000 \leq a \leq 1000a100, 0≤∣b∣≤50000 \leq |b| \leq 50000b5000, 0≤∣c∣≤50000 \leq |c| \leq 50000c5000


Source/Category


Submit Status