【模板】三分 | 函数

题目描述

给定 $n$ 个二次函数 $f_1(x),f_2(x),\dots,f_n(x)$(均形如 $ax^2+bx+c$),设 $F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\}$,求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

输入输出格式

输入格式


输入第一行为正整数 $T$,表示有 $T$ 组数据。 每组数据第一行一个正整数 $n$,接着 $n$ 行,每行 $3$ 个整数 $a,b,c$,用来表示每个二次函数的 $3$ 个系数,注意二次函数有可能退化成一次。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

0.0000
0.5000

说明

对于 $50\%$ 的数据,$n\le 100$。 对于 $100\%$ 的数据,$T<10$,$\ n\le 10^4$,$0\le a\le 100$,$|b| \le 5\times 10^3$,$|c| \le 5\times 10^3$。