曲线(题解)

二分与三分

---

又到了学习代码的时间，这次是在信息学奥赛提高篇上看到的知识点–二分与三分。
二分，即数学中经常使用的二分法，对于区间[a,b]上连续不断且 f(a)·f(b)<0 的函数 y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法叫二分法。

三分，即在区间内用两个mid将区间分成三份,这样的查找算法称为三分查找,也就是三分法,三分法常用于求解单峰函数的最值。同时还有一种理解,即在二分查找的基础上,在左区间或者右区间上再进行一次二分。

二分法适用于单调函数,而三分法用于单峰函数。

样例输入

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

样例输出

0.0000
0.5000

思路

由于函数S是开口向上的二次函数（当a=0时，是一次函数）,由S的定义可知,S或者是一个先单调递减,后单调递增的下凸函数,或者是一个单调函数, F（x）=max(Si(x))也满足单调性。选用三分法很容易求得某个区间内的最小值

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,t;
double a[N],b[N],c[N];
double f(double x)
{
    double maxx=-1e9;
    for (int i=1;i<=n;i++)
      maxx=max(maxx,a[i]*x*x+b[i]*x+c[i]);
    return maxx;
}
int main()
{
    cin>>t;
    for (int i=1;i<=t;i++)
    {
        cin>>n;
        for (int j=1;j<=n;j++) cin>>a[j]>>b[j]>>c[j];
        double l=0,r=1000;
        while (r-l>=1e-11)
        {
            double m1=l+(r-l)/3,m2=r-(r-l)/3;
            if (f(m1)<=f(m2)) r=m2;
            else l=m1;
        }
        cout<<fixed<<setprecision(4)<<f(l)<<endl;   //保留四位小数
    }
    return 0;
}