网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
误差曲线
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | errorcurves.in | 输出文件 | errorcurves.out |
【题目描述】
Josephina是一名聪明的妹子,她最近痴迷于机器学习。她花费了大量精力学习线性判别分析,因为其中有不少有趣的性质。
为了测试算法的性能,她收集了许多数据。每组数据都分成两个部分:训练数据和测试数据。她在训练数据中解算模型的参数,并且在测试数据中测试这个模型。
令她惊讶的是,她发现每组数据的误差曲线都是一条抛物线。一条抛物线对应一个二次函数。在数学中,二次函数指形如f(x)=ax^2+bx+c的多项式函数。如果a=0,二次函数就退化为线性函数。
如果只有一条误差曲线,那么计算最小的误差将非常简单。但这里有多组数据,这意味着Josephina将得到多组误差曲线。Josephina希望调整参数以更好地拟合所有数据。因此她必须统计所有的误差曲线。也就是说,她必须处理许多二次函数,并得出一条新的错误曲线来代表所有的错误。现在,她正关注一个与许多二次函数有关的函数的最小值。
这个新函数定义如下:
F(x)=max{Si(x)},i=1,2,...,n。x的范围是[0,1000]。Si(x)是一个二次函数。
Josephina希望知道F(x)的最小值。不幸的是,用代数方法求解过于复杂。作为一名机智的程序员,你能帮她解决这个问题吗?
【输入格式】
输入包含多组数据。
输入文件的第1行是1个正整数T(T<100),表示数据组数。
每组数据的第1行是一个正整数n(n<=10000)。
接下来的n行,每行有3个正整数a(0<=a<=100),b(|b|<=5000),c(|c|<=5000),描述一个二次方程的相应系数。
【输出格式】
对每组数据,输出一行一个实数,即答案。
【样例输入】
2
1
2 0 0
2
2 0 0
2 -4 2
【样例输出】
0.0000
0.5000
【提示】
答案允许有不超过0.01的误差。
【来源】
刘汝佳,《算法竞赛入门经典训练指南》表2-14