题意：给出n棵树的坐标，树的高度和树的价值，从这些树中砍掉一些（整棵整棵的）做围栏把剩余的树围起来，使得消耗的树的价值最小。输出应砍掉哪里些树以及剩余的材料的长度。（如果砍掉的价值相同，则取砍掉数目少的）(2 <= n <= 15)
题目链接：http://poj.org/problem?id=1873
——>>用二进制映射枚举每种砍树的情况，对于每一种情况，求凸包，求凸包的周长，判断。(这里用G++提交)
注意：1、如果砍掉的价值相同，数目也相同，应砍编号小的树；
2、最后输出时用"%.2f"，千万别用"%.2lf"，多一个l与少一个l区别大大的大！！！（如果结果是0，那么用%lf的话，可能会有-0.00输出，正解应为0.00）
#include <cstdio>
#include <cmath>
#include <algorithm>using namespace std;const int maxn = 15 + 1;
const int INF = 1000000000;struct Tree
{double x;double y;int v;int l;Tree(){}Tree(int xx, int yy):x(xx), y(yy){}bool operator < (const Tree& e) const{return x < e.x || (x == e.x && y < e.y);}
}t[maxn];Tree operator - (Tree A, Tree B){return Tree(A.x - B.x, A.y - B.y);}double Cross(Tree A, Tree B){return A.x * B.y - A.y * B.x;}
double Dis(Tree A, Tree B) {return hypot(A.x - B.x, A.y - B.y);}int ConvexHull(Tree *p, int n, Tree* ch) //求凸包
{sort(p, p + n);int m = 0;for(int i = 0; i < n; i++){while(m > 1 && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) < 0) m--;ch[m++] = p[i];}int k = m;for(int i = n-2; i >= 0; i--){while(m > k && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) < 0) m--;ch[m++] = p[i];}if(n > 1) m--;return m;
}double Perimeter(Tree *ret, int m)
{double perimeter = 0;for(int i = 1; i < m; i++) perimeter += Dis(ret[i], ret[i-1]);perimeter += Dis(ret[0], ret[m-1]);return perimeter;
}int main()
{int n, i, Case = 1, bit;while(scanf("%d", &n) == 1 && n){for(i = 0; i < n; i++) scanf("%lf%lf%d%d", &t[i].x, &t[i].y, &t[i].v, &t[i].l);int min_val = INF; //砍掉的最小价值int min_cnt = INF; //砍掉的最小价值时砍掉的树的数量double exc_len = 0; //做好围栏后剩余木材长度int ans = 0; //砍掉的方法，二进制映射for(bit = 0; bit < (1<<n); bit++) //枚举每一种砍树的方法{Tree buf[maxn], ret[2*maxn]; //buf缓冲，ret求凸包后的点组double cut_len = 0; //这一种方法砍掉的树的总长度int cut_val = 0; //这一种方法砍掉的树的总价值int cut_cnt; //这一种方法砍掉的树的总数量int m = 0; //使用这一种方法后剩下的树的数量for(i = 0; i < n; i++) //扫描这种方法{if(bit&(1<<i)) //被砍掉的{cut_len += t[i].l;cut_val += t[i].v;}else //剩下的{buf[m].x = t[i].x;buf[m++].y = t[i].y;}}if(cut_val > min_val) continue;cut_cnt = n - m;int cnt = ConvexHull(buf, m, ret); //求凸包double perimeter = Perimeter(ret, cnt); //凸包周长if(cut_len >= perimeter) //砍掉的树满足长度要求{if(cut_val < min_val || (cut_val == min_val && cut_cnt < min_cnt)){min_val = cut_val;min_cnt = cut_cnt;exc_len = cut_len - perimeter;ans = bit;}}}if(Case > 1) printf("\n");printf("Forest %d\n", Case++);printf("Cut these trees:");for(i = 0; i < n; i++) if(ans&(1<<i)) printf(" %d", i+1);printf("\n");printf("Extra wood: %.2f\n", exc_len);}return 0;
}