题目链接：
POJ 1873 The Fortified Forest
题意：
有n棵树，知道了每棵树的坐标和高度以及价值，需要砍掉一些树能用这些树的长度对没砍掉的树做成一个围栏，
要保证剩下的树的价值最大，问需要砍掉哪些树，以及围成围栏后剩下的树长度是多少?
n范围2<=n<=15.
分析：
砍完后剩下的树需要的最小围栏长度，就是这些树所形成的凸包的周长。
因为n只有15所以可以dfs枚举砍树的数量，然后检验即可。
弱菜的自述：
因为dfs函数里将dfs(sum,now+1,i+1);写成了dfs(sum,now+1,k+1);成功TLE了第一个发。
又因为在存储砍掉哪些树时，将砍掉的树的数量记成了没砍掉的树的数量，也就是num[0]=sum;写成了num[0]=m;
WA了第二发和第三发！o(╯□╰)o
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
const int MAX_N=50;
const double EPS=1e-10;int n,m,cases=0;
double ans,extra;
int vis[MAX_N],num[MAX_N];struct Tree{double x,y,len,val;Tree () {}Tree (double x,double y) : x(x),y(y) {} Tree operator + (const Tree& rhs) const {return Tree(x+rhs.x,y+rhs.y);}Tree operator - (const Tree& rhs) const {return Tree(x-rhs.x,y-rhs.y);}Tree operator * (const double d) const {return Tree(d*x,d*y);}double cross(const Tree& rhs) const {return x*rhs.y-y*rhs.x;}double dis(const Tree& rhs) const {return sqrt((x-rhs.x)*(x-rhs.x)+(y-rhs.y)*(y-rhs.y));}
};Tree tree[MAX_N],left_tree[MAX_N],res[MAX_N];bool cmp_x(Tree a,Tree b)
{if(abs(a.x-b.x)<EPS) return a.y<b.y;return a.x<b.x;
}inline int Andrew()
{sort(left_tree,left_tree+m,cmp_x);int k=0;for(int i=0;i<m;i++){while(k>1&&(res[k-1]-res[k-2]).cross(left_tree[i]-res[k-1])<=0) k--;res[k++]=left_tree[i];}int tmp=k;for(int i=m-2;i>=0;i--){while(k>tmp&&(res[k-1]-res[k-2]).cross(left_tree[i]-res[k-1])<=0) k--;res[k++]=left_tree[i];}if(k>1) k--; //k=1说明背包退化return k;
}inline void dfs(int sum,int now,int k)
{
//需要砍sum棵树，已经砍了now棵树，正在考虑第k颗树if(now==sum){double sum_len=0,left_val=0;m=0;for(int i=0;i<n;i++){if(vis[i]) sum_len+=tree[i].len;else {left_tree[m++]=tree[i];left_val+=tree[i].val;}}double perimeter;if(m==1){perimeter=0;}else if(m==2){perimeter=2*left_tree[0].dis(left_tree[1]);}else {int total=Andrew();perimeter=0;for(int i=0;i<total;i++){perimeter+=res[i].dis(res[(i+1)%total]);}}//printf("sum=%d sum_len=%.2f perimeter=%.2f\n",sum,sum_len,perimeter);if(sum_len>=perimeter&&left_val>ans){ ans=left_val;extra=sum_len-perimeter;num[0]=sum; //存储被砍掉的树//printf("sum=%d sum_len=%.2f perimeter=%.2f extra=%.2f\n",sum,sum_len,perimeter,extra);int j=1;for(int i=0;i<n;i++){if(vis[i]) num[j++]=i+1;}}}for(int i=k;i<n;i++){vis[i]=1;dfs(sum,now+1,i+1);vis[i]=0;}return;
}int main()
{freopen("Cin.txt","r",stdin);int first=1;while(~scanf("%d",&n)&&n){if(first) first=0;else printf("\n");for(int i=0;i<n;i++){scanf("%lf%lf%lf%lf",&tree[i].x,&tree[i].y,&tree[i].val,&tree[i].len);}ans=extra=-1;for(int i=1;i<n;i++){memset(vis,0,sizeof(vis));dfs(i,0,0);}printf("Forest %d\n",++cases);printf("Cut these trees:");for(int i=1;i<=num[0];i++){printf(" %d",num[i]);}printf("\n");printf("Extra wood: %.2f\n",extra);}return 0;
}