#P3382. 【模板】三分法

【模板】三分法

题目描述

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

输入格式

第一行一次包含一个正整数 NN 和两个实数 l,rl, r,含义如题目描述所示。

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

输出格式

输出为一行,包含一个实数,即为 xx 的值。若你的答案与标准答案的相对或绝对误差不超过 10510^{-5} 则算正确。

3 -0.9981 0.5
1 -3 -3 1
-0.41421

提示

对于 100%100\% 的数据,6N136 \le N \le 13,函数系数均在 [100,100][-100,100] 内且至多 1515 位小数,l,r10|l|,|r|\leq 10 且至多 1515 位小数。lrl\leq r

【样例解释】

如图所示,红色段即为该函数 f(x)=x33x23x+1f(x) = x^3 - 3 x^2 - 3x + 1 在区间 [0.9981,0.5][-0.9981, 0.5] 上的图像。

x=0.41421x = -0.41421 时图像位于最高点,故此时函数在 [l,x][l, x] 上单调增,[x,r][x, r] 上单调减,故 x=0.41421x = -0.41421,输出 0.41421-0.41421