【模板】三分法

qwq这道题其实不用三分做的，直接暴力地用二分做就行了qwq

但是在做二分前，要先了解两个概念：秦九韶公式和函数求导

先讲简单一点的秦九韶公式：

在数学上我觉得没啥大用处，但是在OI里可以吧O(n2)的多项式求值变成O(n)的方法，具体的公式是：

\(a_{1}*x^n+a_{2}*x^{n-1}+a_{3}*x^{n-2}+……+a_{n-1}*x+a_{n}\)

\(=x*(a_{1}*x^{n-1}+a_{2}*x^{n-2}+a_{3}*x^{n-3}+……+a_{n-1})+a_{n}\)

\(=x*(x*(a_{1}*x^{n-2}+a_{2}*x^{n-3}+a_{3}*x^{n-4}+……+)+a_{n-1})+a_{n}\)

\(=\)……

\(=x*(x*(x*(x*……*(a_{1}*x)+a_{2})+a_{3})+a_{4}+……+a_{n-1})+a_{n}\)

就是用乘法分配律乘进去，把O(\(n^2\))弄成了O(n)

inline double f(double t)//秦九韶公式
{
  double ans=k[0]*t+k[1];
  for(int i=2; i<=n; i++)  ans=ans*t+k[i];
  return ans;
}

再讲函数求导：

我自己也讲不清，我就引用一下书上的解释（《高等数学》同济大学出版社，上个世纪80年代出版的，就是我爸的大学数学课本）：

定义：

设函数\(y=f(x)\)在点\(x_{0}\)的某个邻域内有定义，当自变量\(x\)在\(x_{0}\)处取得增量△\(x\)（点\(x_{0}\)+△\(x\)仍在该邻域内）时，相应的函数\(y\)取得增量△\(y=f(x_{0}+x)-f(x_{0})\)；如果△\(y\)与△\(x\)之比当△\(x\)->0时的极限存在，则称函数\(y=f(x)\)在点\(x_{0}\)处可导，并称这个极限为函数\(y=f(x)\)在点\(x_{0}\)处的导数

\(f'(x)=\lim\limits_{\Delta x\rightarrow0}\frac{f(x+\Delta x)-f(x)}{\Delta x}\)

就上面是这个\(f'(x)\)就是\(f(x)\)的导函数qwq

函数的导数可以求直线变速运动的瞬时速度或者切线问题

那么在这道题里我们可以把这个函数图像看成行程图，就是当函数图像在上升的时候，导数为正；图像在下降的时候，导数为负。如果就是在顶点上，那么导数为0，就是零点

零点是什么？嘤嘤嘤就是那个要求的\(x\)啊！qwq！

那么根据这个，就可以二分查找了嘤嘤嘤（查找条件就是左右边界小于精度就行了）

代码：

#include 
using namespace std;
double k[20];
double x,l,r,mid;
long long n;
inline double f(double t)//秦九韶公式求多项式值
{
  double ans=k[0]*t+k[1];
  for(int i=2; i<=n; i++)  ans=ans*t+k[i];
  return ans;
}
/*
我个人比较蒟蒻，不能用数学方法来求导数，
所以说不能作为绝对的△x->0，那么就取一个十分接近0的数，比如1e-8……
*/
inline double lim(double t)
{
  double x,y;
  x=1e-8; y=f(t+x)-f(t);
  return x/y;
}
int main()
{
  cin>>n;
  cin>>l>>r;
  for(int i=0; i<=n; i++) cin>>k[i];
  while(r-l>1e-8)//二分
  {
    mid=(l+r)/2;
    if(lim(mid)>0) l=mid;
    else r=mid;
  }
  printf("%.5lf",mid);
  return 0;
}

嘤嘤嘤再见