信息学奥赛一本通T1435：曲线

【题目描述】

明明做作业的时候遇到了n个二次函数Si(x)= ax2 + 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]上的最小值。精确到小数点后四位，四舍五入。

【输入样例】

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

【输出样例】

0.0000
0.5000

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
const double EPS = 1E-12;
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
int n;
double a[N],b[N],c[N];
double cal(double x){
    double maxx=-INF;
    for(int i=1;i<=n;i++)
        maxx=max(maxx,a[i]*x*x+b[i]*x+c[i]);
    return maxx;
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
        double left=0,right=1000;
        while(right-left>=EPS){
            double lmid=left+(right-left)/3.0;
            double rmid=right-(right-left)/3.0;
            if(cal(lmid)<=cal(rmid))
                right=rmid;
            else
                left=lmid;
        }
        printf("%.4lf\n",cal(left));
    }

    return 0;
}

信息学奥赛一本通T1435：二分与三分 曲线 归属于 二分与三分，更多同类题解源程序见：二分与三分 和 曲线