URAL 1066 Garland 二分

二分H2的位置，判断条件为是否有Hi < 0
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cmath>
 6 
 7 using namespace std;
 8 
 9 const double eps = 1e-9;
10 
11 int N;
12 double A;
13 
14 int dcmp( double a )
15 {
16     if ( fabs(a) < eps ) return 0;
17     return a < 0 ? -1 : 1;
18 }
19 
20 bool cal( double mid, double &ans )
21 {
22     double Hi2 = A, Hi1 = mid, Hi0;
23     for ( int i = 0; i < N - 2; ++i )
24     {
25         Hi0 = 2.0 * ( Hi1 + 1.0 ) - Hi2;
26         if ( dcmp( Hi0 ) < 0 ) return false;
27         Hi2 = Hi1, Hi1 = Hi0;
28     }
29     ans = Hi0;
30     return true;
31 }
32 
33 int main()
34 {
35     while ( ~scanf( "%d%lf", &N, &A ) )
36     {
37         double l = 0.0, r = A;
38         //int cnt = 0;
39         double ans;
40         while ( dcmp( r - l ) > 0 )
41         {
42             //++cnt;
43             double mid = ( l + r ) / 2.0;
44             //printf( "%f %f %f
", l, r, mid );
45             double tmp;
46             if ( !cal( mid, tmp ) ) l = mid;
47             else
48             {
49                 r = mid;
50                 ans = tmp;
51             }
52             //if ( cnt > 100 ) break;
53         }
54         printf( "%.2f
", ans );
55     }
56     return 0;
57 }