hdu3714 Error Curves---三分复习

Error CurvesTime Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1151    Accepted Submission(s): 440


Problem Description

It's very easy to calculate the minimal error if there is only one test error curve. However, there are several datasets, which means Josephina will obtain many parabolic curves. Josephina wants to get the tuned parameters that make the best performance on all datasets. So she should take all error curves into account, i.e., she has to deal with many quadric functions and make a new error definition to represent the total error. Now, she focuses on the following new function's minimum which related to multiple quadric functions. The new function F(x) is defined as follows: F(x) = max(Si(x)), i = 1...n. The domain of x is [0, 1000]. Si(x) is a quadric function. Josephina wonders the minimum of F(x). Unfortunately, it's too hard for her to solve this problem. As a super programmer, can you help her?InputOutputSample InputSample OutputAuthorSourceRecommend#include<iostream>#include<cstdlib>#include<stdio.h>#include<algorithm>#include<math.h>#define eps 1e-15const int N=10010;using namespace std;double a[N],b[N],c[N];int n;double cal(double xx){ double ans=a[0]*xx*xx+b[0]*xx+c[0]; for(int i=1;i<n;i++) ans=max(ans,a[i]*xx*xx+b[i]*xx+c[i]); return ans;}double solve(){ double left,right; double mid,midmid; double mid_area,midmid_area; left=0;right=1000; while(left+eps<right) { mid=(left+right)/2; midmid=(mid+right)/2; mid_area=cal(mid); midmid_area=cal(midmid); if(mid_area>midmid_area) left=mid; else right=midmid; } return cal(right);}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&c[i]); double f=solve(); printf("%.4lf\n",f); }}