[暑假集训]Day5 T3 曲线

问题 C: 曲线

时间限制: 1 Sec 内存限制: 512 MB

题目描述

明明做作业的时候遇到了 n 个二次函数 Si(x)=ax^2+bx+c，他突发奇想设计了一个新的函数 F(x)=max（Si(x)）,i=1…n。
明明现在想求这个函数在 [0,1000]的最小值，要求精确到小数点后四位，四舍五入。

输入

输入包含 T 组数据（T＜10），每组第一行一个整数 n；（n≤10000）
接下来 n 行，每行 3 个整数 a（0≤a≤100）, b（|b|≤5000）, c（|c|≤5000），分别用来表示每个二次函数的 3 个系数。注意：二次函数有可能退化成一次。

输出

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

样例输入

样例输出

0.0000
0.5000

提示

对于 50% 的数据，n≤100
对于 100% 的数据，T＜10,n≤10000, 0≤a≤100,∣b∣≤5000,∣c∣≤5000。

思路：不太难的一道裸三分，只要理解了二次函数就不难。因为在网上找了个错误的板子，所以调了将近一下午吧，感谢DJY和CZD帮我最终调对了这道题。

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t,n;
 4 double a[10005],b[10005],c[10005];
 5 double flag=1e-9;
 6 void init()
 7 {
 8     for(int i=1;i<10001;i++) a[i]=b[i]=c[i]=0.0;
 9 }
10 double count(double x)
11 {    
12     double ans=a[1]*x*x+b[1]*x+c[1];
13     for(int i=2;i<=n;i++) ans=max(ans,(double)a[i]*x*x+b[i]*x+c[i]);
14     return ans;
15 }
16 int main()
17 {
18     scanf("%d",&t);
19     while(t--)
20     {
21         init(); 
22         scanf("%d",&n);
23         for(int i=1;i<=n;i++) 
24         {
25             scanf("%f%f%f",&a[i],&b[i],&c[i]);
26         }
27         double l_mid,r_mid;
28         double l=0,r=1000;
29         while(r-l>flag)
30         {        
31             l_mid=l+(r-l)/3.0;
32             r_mid=r-(r-l)/3.0;
33             if(count(l_mid)>count(r_mid)) l=l_mid;
34             else r=r_mid;
35         }
36         printf("%.4f
",count(l));
37         continue;
38     }
39     return 0;
40 }