題目：在二維平面上有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.2cto.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; }
