洛谷 P3382 【模板】三分法

https://www.luogu.org/problemnew/show/3382

（dcmp是个好东西）

先增后减求极大。

如果f(lm)大于f(rm)，那么答案在[l,rm]之间

否则答案在[lm,r]之间

（在这里，等于无所谓）

如果先减后增求极小，则大于和小于交换。（如果忘了，画张函数图像，举些特例就知道了）

曾经错误：见注释掉的代码

#include<cstdio>
#include<cmath>
using namespace std;
const double eps=1e-8;
int dcmp(double x)
{
    if(fabs(x)<eps)    return 0;
    return x<0?-1:1;
}
int n;
double a[20],l,r;
double getans(double x)
{
    double b=1,ans=a[n+1];
    for(int i=1;i<=n;i++)
    {
        b*=x;
        ans+=b*a[n-i+1];
    }
    return ans;
}
int main()
{
    int i;
    double lm,rm,d1,d2;
    scanf("%d%lf%lf",&n,&l,&r);
    for(i=1;i<=n+1;i++)
        scanf("%lf",&a[i]);
    while(dcmp(r-l)>0)
    {
        lm=l+(r-l)/3;
        rm=r-(r-l)/3;//rm=lm+(r-l)/3;
        d1=getans(lm);
        d2=getans(rm);
        if(d1>d2)
            r=rm;//r=d2;
        else
            l=lm;//l=d1;
    }
    printf("%.5lf",(l+r)/2);
    return 0;
}