uvalive 5009 Error Curves

解题思路：三分
  1 ///////////////////////////////////////////////////////////////////////////
  2 //problem_id: uvalive 5009
  3 //user_id: SCNU20102200088
  4 ///////////////////////////////////////////////////////////////////////////
  5 
  6 #include <algorithm>
  7 #include <iostream>
  8 #include <iterator>
  9 #include <iomanip>
 10 #include <cstring>
 11 #include <cstdlib>
 12 #include <string>
 13 #include <vector>
 14 #include <cstdio>
 15 #include <cctype>
 16 #include <cmath>
 17 #include <queue>
 18 #include <stack>
 19 #include <list>
 20 #include <set>
 21 #include <map>
 22 using namespace std;
 23 
 24 ///////////////////////////////////////////////////////////////////////////
 25 #pragma comment(linker,"/STACK:1024000000,1024000000")
 26 
 27 #define lson l,m,rt<<1
 28 #define rson m+1,r,rt<<1|1
 29 ///////////////////////////////////////////////////////////////////////////
 30 
 31 ///////////////////////////////////////////////////////////////////////////
 32 const double EPS=1e-9;
 33 const double PI=acos(-1.0);
 34 const double E=2.7182818284590452353602874713526;
 35 
 36 const int x4[]={-1,0,1,0};
 37 const int y4[]={0,1,0,-1};
 38 const int x8[]={-1,-1,0,1,1,1,0,-1};
 39 const int y8[]={0,1,1,1,0,-1,-1,-1};
 40 ///////////////////////////////////////////////////////////////////////////
 41 
 42 ///////////////////////////////////////////////////////////////////////////
 43 typedef long long LL;
 44 
 45 typedef int T;
 46 T max(T a,T b){ return a>b? a:b; }
 47 T min(T a,T b){ return a<b? a:b; }
 48 T gcd(T a,T b){ return b==0? a:gcd(b,a%b); }
 49 T lcm(T a,T b){ return a/gcd(a,b)*b; }
 50 ///////////////////////////////////////////////////////////////////////////
 51 
 52 ///////////////////////////////////////////////////////////////////////////
 53 //Add Code:
 54 int n,a[10005],b[10005],c[10005];
 55 
 56 double cal(double x){
 57     double ret=-1e12;
 58     for(int i=1;i<=n;i++){
 59         double temp=a[i]*x*x+b[i]*x+c[i];
 60         ret=max(ret,temp);
 61     }
 62     return ret;
 63 }
 64 
 65 double sanfen(){
 66     double l=0,r=1000;
 67     while(r-l>EPS){
 68         double m1=l+(r-l)/3,m2=r-(r-l)/3;
 69         if(cal(m1)<cal(m2)) r=m2;
 70         else l=m1;
 71     }
 72     return l;
 73 }
 74 ///////////////////////////////////////////////////////////////////////////
 75 
 76 int main(){
 77     ///////////////////////////////////////////////////////////////////////
 78     //Add Code:
 79     int Case,i;
 80     scanf("%d",&Case);
 81     while(Case--){
 82         scanf("%d",&n);
 83         for(i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
 84         double x=sanfen();
 85         printf("%.4lf
",cal(x));
 86     }
 87     ///////////////////////////////////////////////////////////////////////
 88     return 0;
 89 }
 90 
 91 ///////////////////////////////////////////////////////////////////////////
 92 /*
 93 Testcase:
 94 Input:
 95 2
 96 1
 97 2 0 0
 98 2
 99 2 0 0
100 2 -4 2
101 Output:
102 0.0000
103 0.5000
104 */
105 ///////////////////////////////////////////////////////////////////////////