【模板】三分法（洛谷P3382）

Description

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

Input

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

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

Output

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

Solution

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
double l,r,x[100];
double calc(double t)
{
	double ans=x[n+1],X=1;
	for (int i=n;i>=1;i--)
	{
		X=X*t;
		ans=ans+x[i]*X;
	}
	return ans;
}
int main()
{
	scanf("%d%lf%lf",&n,&l,&r);
	for (int i=1;i<=n+1;i++) scanf("%lf",&x[i]);
	for (int i=1;i<=100;i++)
	{
		double mid1=(l+r)/2,mid2=(mid1+r)/2;
		if (calc(mid1)>calc(mid2)) r=mid2;
		else l=mid1;
	}
	printf("%.5lf
",l);
	return 0;
}