poj1873

题意：给定一些树木的坐标及砍掉树木所能围成的长度，还有他的价值，问在损失最少的价值的情况下砍掉那些树，使得砍掉的树足够围住剩下的树。。
思路：枚举砍掉的树，然后进行一次凸包，判断即可
code：
  1 /*
  2   State: Accepted
  3   Time:  2013-03-30 17:27:14
  4 */
  5 
  6 #include <iostream>
  7 #include <cmath>
  8 #include <cstring>
  9 #include <cstdlib>
 10 #include <cmath>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <set>
 14 #define M0 memset(a, 0 ,sizeof(a))
 15 struct oo {int x ,y , l, v;};
 16 using namespace std;
 17 oo a[100], b[100], q[100];
 18 int n ,  tot, ansv , ansopt , px , py , test = 0,ansnum;
 19 double anslen;
 20 void init(){
 21    anslen = 0;
 22    ansv = ansopt = 0;
 23    ansnum = 0x7fffffff;
 24    memset(a, 0 ,sizeof(a));
 25    for (int i = 1;  i <= n; ++i)
 26       scanf("%d%d%d%d",&a[i].x, &a[i].y, &a[i].v ,&a[i].l); 
 27      
 28 }
 29 
 30 bool cmp(const oo a, const oo b){
 31      if (a.x  < b.x|| a.x == b.y && a.y < b.y ) return true;
 32      return false;
 33 }
 34      
 35 bool cmpx(const oo a, const oo b){
 36      int x1 = a.x - px;
 37      int x2 = b.x - px;
 38      int y1 = a.y - py;
 39      int y2 = b.y - py;
 40      if (x1 * y2 -x2* y1 > 0) return true;
 41      if (x1*y2 - x2*y1 == 0 && x1*x1 + y1*y1 < x2*x2 +y2*y2) return true;
 42      return false;
 43 }
 44 
 45 void solve(int opt){
 46      tot = 0;
 47      oo c;
 48      memset(b, 0, sizeof(b));
 49      int value = 0 , len = 0;
 50      int x1 , y1, x2, y2;
 51      double x,y;
 52      for (int i = 1;  i <= n; ++i){
 53          if  (((1 << i) & opt )!= 0){
 54               b[++tot] = a[i];
 55               value += a[i].v;  
 56          }
 57         else  len += a[i].l;
 58      }
 59      if (value < ansv) return;
 60      sort(b+1, b+1+tot, cmp);
 61     for (int i = 2; i < tot; ++i)
 62        for (int j = i + 1; j <= tot;  ++j )
 63          if (!cmpx(a[i], a[j])) {
 64               c = a[i];
 65               a[i] = a[j];
 66               a[j] = c;
 67          }
 68     // if (tot > 2) sort(b + 2, b + tot + 1, cmpx);
 69      memset(q, 0 ,sizeof(q));
 70      q[1] = b[1];
 71      q[2] = b[2];
 72      int h = 1 , t = 2;
 73      for (int i = 3;  i <= tot; ++i){
 74           while (t > h){
 75                x1 = b[i].x - q[t-1].x;
 76                x2 = q[t].x - q[t-1].x;
 77                y1 = b[i].y - q[t-1].y;
 78                y2 = q[t].y - q[t-1].y;
 79                if (x1*y2-x2*y1 > 0) -- t;
 80                else break;
 81           }
 82           q[++t] = b[i];
 83      }
 84       if (tot == 1) t = 1;
 85      q[++t] = b[1];
 86      double len1 = 0;
 87      for (int i = 2; i <= t; ++i){
 88          x = q[i].x - q[i-1].x;
 89          y = q[i].y - q[i-1].y;
 90          len1 += (pow(x*x+y*y,0.5));
 91      }
 92      
 93      if (len >= len1){
 94           if (ansv < value || ansv == value && ansnum > n - tot){   
 95               ansv = value;
 96               ansopt = opt;   
 97               anslen = len - len1;
 98               ansnum = n - tot;
 99           }
100      }
101 }
102 
103 void dfs(int i, int opt){
104     if (i > n) {
105        solve(opt); 
106        return;
107     }
108     dfs(i + 1, opt);
109     dfs(i + 1, opt |(1 << i) );
110 
111 }
112 
113 void print(){
114     printf("Forest %d\nCut these trees: ",test);
115     for (int i =1; i <= n; ++i)
116     if (((1 << i)&ansopt) == 0)
117         printf("%d ",i);
118     printf("\nExtra wood: %.2lf\n\n",anslen);
119         
120 }
121 
122 int main(){
123     freopen("poj1873.in","r",stdin);
124     freopen("poj1873.out","w",stdout);
125     while ( scanf("%d",&n) != EOF && n != 0)
126     {
127         ++test;
128         init();
129         dfs(1, 0);
130         print();
131     }   
132     fclose(stdin); fclose(stdout);
133 }