【模板】三分法

对比于二分法，三分法的适用范围要略窄一些，但是并不是代表它没有用，在一些题目中还是有很大用处的。。。

三分法是用来求一个凸性函数的方法，所谓凸性函数就是一个函数在某一区间内有最大值，最大值两侧各具有单调性，并且单调性相反。

题目大意：

给出一个N次函数，保证在范围[l,r]内存在一点x，使得[l,x]上单调增，[x,r]上单调减。试求出x的值

输入格式：

第一行一次包含一个正整数N和两个实数l、r，含义如题目描述所示

第二行包含N+1个实数，从高到低依次表示该N次函数各项的系数

输出格式：

输出为一行，包含一个实数，即为x的值。四舍五入保留5位小数。

首先，我们先求出l和r的中点mid，再求出mid和r的中点midd，分别将mid和midd代入式子，判断那个值大，舍弃值小的一段区间[l,mid]或[midd,r],然后接着三分直到找到答案为止。正确性还是比较显然的，如果mid与midd同侧，那么显然大的值更靠近x，如果异侧也是同理的（当然我们是无法知道同侧还是异侧的。。。）

最后，附上本题代码：

#include<cstdio>
#define maxn 13
using namespace std;

const double eps=1e-8;
int n;
double a[maxn+5];
double l,r;

double check(double x)
{
    double ans=a[n+1];
    for(int i=n; i>=1; i--)
    {
        double temp=a[n-i+1];
        for(int j=1; j<=i; j++)
        {
            temp*=x;
        }
        ans+=temp;
    }
    return ans;
}
int main()
{
    scanf("%d%lf%lf",&n,&l,&r);
    for(int i=1; i<=n+1; i++)
    {
        scanf("%lf",&a[i]);
    }
    while(r-l>eps)
    {
        double mid=(r+l)/2,midd=(mid+r)/2;
        if(check(mid)>check(midd))
        {
            r=midd;
        }
        else
        {
            l=mid;
        }
    }
    printf("%.5lf",l);
    return 0;
}