题解0003：曲线

题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1435

题目描述：一个函数F(x)=max(Si(x))">F(x)=max(Si(x)) （Si(x)=ax^2+bx+c），i=1,2...n">i=1,2...ni=1,2...n；输出函数F(x)">F(x)的在区间[0,1000">0,1000]上的最小值

0,1000">题目思路：三分求解，将范围分成3份，判断左右哪边比较小，然后缩小范围，求出最小值

0,1000">代码：

#include
using namespace std;
#define INF 0X3F3F3F3F
double l=1000,r=0,eps=1e-11,a[10001],b[10001],c[10001],lmid,rmid;
int n,t;
double Q(double x){
	double maxl=-INF;//int最小值
	for(int i=1;i<=n;i++){
		maxl=max(maxl,a[i]*x*x+b[i]*x+c[i]);//求出max(Si(x))
	}
	return maxl;
}
int main(){
	int i;
	cin>>t;
	for(int k=0;k;k++){
		cin>>n;
		for(i=1;i<=n;i++){
			cin>>a[i]>>b[i]>>c[i];	
		}
		l=0;
		r=1000;
		while(l+eps){//三分，只要l和r的差距不小于1e-11就一直循环
			lmid=l+(r-l)/3;//左边
			rmid=r-(r-l)/3;//右边
			if(Q(lmid)<=Q(rmid)){//调用Q函数判断哪个小
				r=rmid;
			}else{
				l=lmid;
			}//缩小范围
		}
		printf("%.4lf\n",Q(l));//输出，保留四位
	}
	return 0;
}