模板---三分法

原题为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;
}