题目来源：
http://poj.org/problem?id=1873
题意：给出n棵树的坐标，树的高度和树的价值，从这些树中砍掉一些（整棵整棵的）做围栏把剩余的树围起来，使得消耗的树的价值最小。输出应砍掉哪里些树以及剩余的材料的长度。（如果砍掉的价值相同，则取砍掉数目少的）(2 <= n <= 15)。
1：因为只有15棵树，用位运算枚举砍树情况就行了。
2：枚举时注意剪枝
3：当剩下的点集处理凸包时m<=1 时特殊处理下
代码如下：
#include <iostream> #include <algorithm> #include <stdlib.h> #include <iostream> #include <stdio.h> #include <stack> #include <string> #include <string.h> #include <algorithm> #include <stdlib.h> #include <vector> #include <set> #include <math.h> #include <cmath> #include <map> #include <queue> using namespace std ; typedef long long LL; const int inf=0x7fffffff; const int N = 20; double EPS= 1e-10; double add(double a, double b) { if( fabs(a+b)< EPS * ( fabs(a)+fabs(b) ) ) return 0; return a+b; } struct Point{ double x,y; int v,l; double dist(Point p){ return sqrt( add( ( x-p.x)*(x-p.x) , (y-p.y)*(y-p.y) ) ); } }; // pop1*p0p2 > 0 左转 double xmult(Point p1, Point p2, Point p0){ return add( (p1.x-p0.x)*(p2.y-p0.y), -(p1.y-p0.y)*(p2.x-p0.x) ); } Point List[N]; // 点集 int top; // 栈顶指针 Point qs[N]; Point p[N]; bool operator<(Point a, Point b) // 按y轴值从小到大， y轴值相同时，x轴从小到大排列 { if(a.y != b.y) return a.y< b.y; else return a.x < b.x; } // 这种基于平面扫描法的graham扫描算法中， qs中存储的是起点然后回到起点qs[0]=qs[top]=起点 double graham(int n) { sort(List,List+n); double sum=0; if(n==0 || n==1) return 0; // 特殊处理下 qs[0]=List[0]; qs[1]=List[1]; top=1; //构造凸包的下侧 for(int i=2; i<n;i++){ while(top>=1 && xmult( qs[top],List[i],qs[top-1] )<=0 ) top--; qs[++top]=List[i]; } //构造凸包的上侧 qs[++top]=List[n-2]; int len=top; for(int i=n-3 ;i>=0 ; i--){ while(top>=len && xmult( qs[top],List[i],qs[top-1] )<=0 ) top--; qs[++top]=List[i]; } for(int i=0 ; i<top ; i++) sum+=qs[i].dist(qs[i+1]); return sum; } // 二进制枚举 void solve(int n,int &min_val, int &cut_num, double &re_len, int &ans) { for(int bit=0; bit<(1<<n); bit++) // 二进制枚举 { int t=0,cut_val=0; double cut_len=0 ; for(int i=0; i<n; i++){ if(bit & (1<<i)) { cut_len+=p[i].l; cut_val+=p[i].v; } else { List[t].x=p[i].x; List[t++].y=p[i].y; } } if(cut_val > min_val) continue; // 一个重要的剪枝 double c=graham(t); if(cut_len >=c ) // 满足长度限制，也算个剪枝吧 { if(cut_val < min_val || (cut_val== min_val && n-t < cut_num)) { min_val=cut_val; cut_num=n-t; ans=bit; re_len=cut_len-c; } } } } int main() { int n,k=1; int flag=1; while(scanf("%d",&n),n) { if(!flag) {puts("");} flag=0; for(int i=0; i<n; i++) scanf("%lf%lf%d%d",&p[i].x,&p[i].y, &p[i].v, &p[i].l); int min_val=inf; int cut_num=inf; double re_len=0; int ans=0; solve(n,min_val,cut_num,re_len,ans); printf("Forest %d ",k++); printf("Cut these trees:"); for(int i=0 ; i<n; i++){ if(ans & (1<<i)) printf(" %d",i+1); } printf(" Extra wood: %.2lf ",re_len); } return 0; }