hdu--5135--贪心

尽量选边数大的3根木棍来组成一个三角形一直到无法选取为止
这边计算三角形面积还是用海伦公式比较方便
 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <iomanip>
 6 using namespace std;
 7 
 8 double Abs( double x )
 9 {
10     return x>=0? x : -x;
11 }
12 
13 double a[15];
14 bool vis[15];
15 
16 int main()
17 {
18     cin.sync_with_stdio(false);
19     int n;
20     double x , y , z , ans;
21     while( cin >> n && n )
22     {
23         for( int i = 0 ; i<n ; i++ )
24         {
25             cin >> a[i];
26         }
27         memset( vis , false , sizeof(vis) );
28         sort( a , a+n );
29         ans = 0;
30         for( int i = n-1 ; i>=2 ; i-- )
31         {
32             if( !vis[i] )
33             {
34                 x = a[i];
35                 y = z = -1;
36                 int j = i-1;
37                 while( j>=0 )
38                 {
39                     if( !vis[j] )
40                     {
41                         y = a[j];
42                         break;
43                     }
44                     -- j;
45                 }
46                 int k = j-1;
47                 while( k>=0 )
48                 {
49                     if( !vis[k] )
50                     {
51                         z = a[k];
52                         break;
53                     }
54                     -- k;
55                 }
56                 if( y!=-1 && z!=-1 && y+z>x )
57                 {
58                     double mid = ( x + y + z ) / 2;
59                     ans += sqrt( mid * Abs(mid-x) * Abs(mid-y) * Abs(mid-z) );
60                     vis[i] = vis[j] = vis[k] = true;
61                 }
62             }
63         }
64         cout << setiosflags(ios::fixed);
65         cout << setprecision(2) << ans << endl;
66     }
67     return 0;
68 }
View Code