HDU 3714 Error Curves

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3714

这题我死活没读懂什么意思，后来还是别人讲的我才明白。

题目：给出一组一元二次方程，用这一组一元二次方程生成一个新的函数F(x)，求F(x)的最小值。x 对应F(x) 的值=这一组一元二次方程中y_i = a_i * x^2 + b_i * x + c_iy最大的那一个。

分析：凹函数求极值，三分法。

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 struct node
 5 {
 6     int a, b, c;
 7 };
 8 
 9 const int MAXN = 10000 + 10;
10 const double EXP = 1e-12;
11 const double INF = 2147483646;
12 
13 int n;
14 node D[MAXN];
15 
16 double calcu( double x )
17 {
18     double ans = -INF;
19     double temp;
20 
21     for ( int i = 0; i < n; i++ )
22     {
23         temp = D[i].a * x * x + D[i].b * x + D[i].c;
24         if ( temp > ans ) ans = temp;
25     }
26 
27     return ans;
28 }
29 
30 double Solve()
31 {
32     double Left = 0, Right = 1000;
33     double mid, midmid;
34     double mid_value, midmid_value;
35 
36     while ( Left + EXP < Right )
37     {
38         mid = ( Left + Right ) / 2;
39         midmid = ( mid + Right ) / 2;
40         mid_value = calcu(mid);
41         midmid_value = calcu(midmid);
42 
43         if ( mid_value <= midmid_value ) Right = midmid;
44         else Left = mid;
45     }
46 
47     return calcu(Left);
48 }
49 
50 int main()
51 {
52     int T;
53     scanf( "%d", &T );
54     while( T-- )
55     {
56         scanf( "%d", &n );
57         for ( int i = 0; i < n; i++ )
58            scanf( "%d%d%d", &D[i].a, &D[i].b, &D[i].c );
59 
60         printf( "%.4f\n", Solve() );
61     }
62     return 0;
63 }