模板---三分法

原题为luogu3382，传送门
给出一个N次函数$f$，保证在范围$[l,r]$内存在一点$x$，使得$[l,x]$上单调增，$[x,r]$上单调减。试求出$x$的值。

算法过程

三分法流程：
在区间$[L,R]$中选取两个点$l,r$，保证$L \le l \le r \le R$，若$f(l)>f(r)$，则再对$[L,r]$进行三分，否则对$[l,R]$进行三分。
显然，当$f(l)>f(r)$，若$x$在$[r,R]$中，则$f(l)>f(r) \le f(x) \ge f(r)$并不满足单调性，一定不可能。
$f(l)<f(r)$也一样.
$l,r$可以是$[L,R]$的三等分点，也可以$l$是$[L,R]$的中点，$r$是[l,R]的中点等。
当然我写的是第一种。
核心代码如下：

const double eps=1e-6;
double a[20];
int n;
double f(double x){
    double sum=0;
    up(i,0,n)sum=sum*x+a[i];

}
int main(){
    double l,r,z,y;
    cin>>n>>l>>r;

    up(i,0,n)cin>>a[i];
    while(r-l>eps){
        z=(l*2+r)/3,y=(l+r*2)/3;
        if(f(z)<f(y))l=z;
        else r=y;
    }
    printf("%.5lf\n",l);
    return 0;
}