UVa 811 - The Fortified Forest

题目：在二维平面上有n棵树，每棵树有自己的高度和价值。从里面砍掉一些，做成围栏（围栏的长度都与被砍掉树的高度和），问砍掉的最小价值是多少，如果价值相同，取砍掉树数目最少的。
 
分析：状态压缩、计算几何、凸包。如果搜索显然后超时（15!），利用2进制状态表示树砍和不砍的状态，例如：5(10)=101(2)表示1、3被砍掉，则一共有1<<15种状态，然后计算每种状态下未被砍掉的树的凸包以及被砍掉树的高和，比较即可。
 
注意：线段的周长等于二倍的线段长。
 
[cpp]  
#include <algorithm>  
#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
#include <cmath>  
  
using namespace std;  
  
//点结构   
typedef struct pnode  
{  
    int x,y,v,l,d;  
}point;  
point I[16];  
point P[16];  
  
//叉乘ab*ac   
int crossproduct( point a, point b, point c )  
{  
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);  
}  
  
//点到点距离   
int dist( point a, point b )  
{  
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);  
}  
  
//坐标排序   
bool cmp1( point a, point b )  
{  
    return (a.x==b.x)?(a.y<b.y):(a.x<b.x);  
}  
  
//级角排序    www.zzzyk.com
bool cmp2( point a, point b )  
{  
    double cp = crossproduct( P[0], a, b );  
    if ( !cp ) return a.d < b.d;  
    else return cp > 0;  
}  
  
//计算凸包   
double Graham( int n )  
{  
    sort( P+0, P+n, cmp1 );  
    for ( int i = 1 ; i < n ; ++ i )  
        P[i].d = dist( P[0], P[i] );  
    sort( P+1, P+n, cmp2 );  
      
    int top = n-1;  
    if ( n > 2 ) {  
        top = 1;  
        for ( int i = 2 ; i < n ; ++ i ) {  
            while ( top > 0 && crossproduct( P[top-1], P[top], P[i] ) <= 0 ) -- top;  
            P[++ top] = P[i];  
        }  
    }  
    P[++ top] = P[0];  
      
    double L = 0.0;  
    for ( int i = 0 ; i < top ; ++ i )  
        L += sqrt(dist( P[i], P[i+1] )+0.0);  
    return L;  
}  
  
int main()  
{  
    int n,t = 0;  
    while ( scanf("%d",&n) && n ) {  
        for ( int i = 0 ; i < n ; ++ i )  
            scanf("%d%d%d%d",&I[i].x,&I[i].y,&I[i].v,&I[i].l);  
          
        double MinV = 0x7ffffff,MinL = 0.0;  
        int E = (1<<n)-1,S = 0,C = n;  
        for ( int i = 0 ; i < E ; ++ i ) {  
            int count = 0,cut = 0;  
            int SumL = 0,SumV = 0;  
            for ( int j = 0 ; j < n ; ++ j )  
                if ( i&(1<<j) ) {  
                    SumL += I[j].l;  
                    SumV += I[j].v;  
                    cut ++;  
                }else P[count ++] = I[j];  
              
            double V = Graham( count );   
            if ( V<=SumL && (SumV<MinV || (SumV==MinV&&cut<C)) ) {  
                MinV = SumV;  
                MinL = SumL-V;  
                C = cut;  
                S = i;  
            }  
        }  
          
        if ( t ++ ) printf("\n");  
        printf("Forest %d\nCut these trees:",t);  
        for ( int i = 0 ; i < n ; ++ i )  
            if ( S&(1<<i) ) printf(" %d",i+1);  
        printf("\nExtra wood: %.2lf\n",MinL);  
          
    }  
    return 0;  
}

补充：软件开发 , C++ ,