三分求函数极值

这篇博客是个极其简单的东西。

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

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

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

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

输入
3 -0.9981 0.5
1 -3 -3 1

输出
-0.41421

三分主要就是用于求函数极值，当然只用于求凸函数或者凹函数的极值。

尽管求这个东西可以通过对函数求导，再二分。。。嘤嘤嘤，但是对于有些麻烦的函数，求导是很不方便的，而且也没有复杂度的优势。

对于上面这个凸函数，我们每次取三分之一点 m1 和 三分之二点 m2 然后我们通过比较两点之间的函数值然后让 l ，r 逼近极值即可。

double f_max(){
	while(fabs(l-r)>1e-7){
		double mid=(l+r)/2;
		if(f(mid-eps)<f(mid+eps))	l=mid;
		else r=mid;
	}
	return l;
}

为什么上面的代码没有取三分之一和三分之二点呢？其实三分之二和三分之一只是理论点，但是在实际情况中，我们一般取中点附件更快哦！！！

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const double eps=1e-8;
int n;
double l,r,a[20];
double f(double x){
	double res=0;
	for(int i=n;i>=0;i--)	res=res*x+a[i];
	return res;
}
double f_max(){
	while(fabs(l-r)>1e-7){
		double mid=(l+r)/2;
		if(f(mid-eps)<f(mid+eps))	l=mid;
		else r=mid;
	}
	return l;
}
signed main(){
	cin>>n>>l>>r;
	for(int i=n;i>=0;i--)	cin>>a[i];
	printf("%.5lf\n",f_max()+0.0000005);
	return 0;
}