三分模板

/***********
P3382 【模板】三分法
***********/
#include <bits/stdc++.h>
using namespace std;

const int N = 20;
double a[N];
int n;
double f(double x) //此处可以用秦九韶算法简化为O（n）的！
{
    double ans = 0;
    for(int i=1; i<=n+1; i++)
    {
        ans += 1.0 * pow(x,n - i + 1) * a[i];
    }
    return ans;
}

int main()
{
    double l,r;
    cin >> n >> l >> r;
    for(int i=1; i<=n+1; i++) cin >> a[i];
    double ans = 0;
    while(r - l > 1e-7)
    {
        double lmid = l + (r - l) / 3,rmid = r - (r - l) / 3;
        if(f(lmid) >= f(rmid)) r = rmid,ans = rmid;
        else l = lmid;
    }
    printf("%.6f\n",ans);
    return 0;
}