UVA1476 三分法

单峰函数（即先递增后递减，有极大值的函数），都可以用三分法来求

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <algorithm>
#define Max 2147483647
#define INF 0x7fffffff
#define N 90010
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define repu(i, a, b) for(int i = (a); i < (b); i++)
const double PI=-acos(-1.0);
using namespace std;
int a[N],b[N],c[N],T,n;
double f(double x)///寻找最大值
{
    double ans = a[0]*x*x+b[0]*x+c[0];
    repu(i,1,n)
    ans = max(ans,a[i]*x*x+b[i]*x+c[i]);
    return ans;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        repu(i,0,n)
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        double l =0.0000,r=1000.000;
        repu(i,0,100)
        {
            double m1 = l+(r-l)/3;
            double m2 = r-(r-l)/3;
            if(f(m1)<f(m2))///如果m2更大，说明在r的范围需要更靠左
                r= m2;
            else
                l = m1;
        }
        printf("%.4lf
",f(l));
    }
    return 0;
}