题意：一个人有好多树，这些树有坐标，有价值，以及砍下这颗树能造多长的篱笆。
现在他要保护自己的树不被别人砍，就需要用篱笆把树围起来，但是需要从自己的树中砍下来几棵树造成篱笆，所以问题就来了，如何砍最少价值的树把剩余的树围起来。如果价值一样，就找砍树数量少的。
看到这道题的数据范围我就笑了，直接指数级别的枚举就行了。然后求凸包。
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 1111111
#define MAXM 104444
#define INF 100000000
#define eps 1e-7
#define L(X) X<<1
#define R(X) X<<1|1
using namespace std;
typedef double T;
struct POINT
{T x;T y;POINT() : x(0), y(0) {};POINT(T _x_, T _y_) : x(_x_), y(_y_) {};
};
POINT p[555], s[555];
T x[555], y[555], l[555];
int v[555];
T DIS(const POINT & a, const POINT & b)
{return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
T CROSS(const POINT & a, const POINT & b, const POINT & o)
{return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
bool cmp(const POINT & A, const POINT & B)
{T CR = CROSS(A, B, p[0]);if(CR > 0) return true;if(CR == 0) return DIS(A, p[0]) < DIS(B, p[0]);return false;
}
struct ant
{int a[18];int cnt, v;double len;void init(){ cnt = 0; len = 0; v = 0;}
};
int main()
{int n;int cas = 0;while(scanf("%d", &n) != EOF && n){if(cas) printf("\n");for(int i = 0; i < n; i++)scanf("%lf%lf%d%lf", &x[i], &y[i], &v[i], &l[i]);int bd = (1 << n);ant ans;ans.init();ans.v = INF;T fk = 0;for(int j = 0; j < bd; j++){int cnt = 0;int ti = j;ant tx;tx.init();int tn = 0;double need = 0;while(cnt < n){if(ti & 1){tx.a[tx.cnt ++] = cnt;tx.len += l[cnt];tx.v += v[cnt];}else{p[tn].x = x[cnt];p[tn++].y = y[cnt];need += l[cnt];}ti >>= 1;cnt++;}T xx = INF, yy = INF;int tmp;//for(int i = 0; i < tx.cnt; i++)//printf("%d ", tx.a[i]);//printf("\n");for(int i = 0; i < tn; i++){//printf("ss %.3f %.3f\n", p[i].x, p[i].y);if(p[i].x < xx || p[i].x == xx && p[i].y < yy){xx = p[i].x;yy = p[i].y;tmp = i;}}double cir = 0;if(tn == 0 || tn == 1) cir = 0;else if(tn == 2) cir = 2.0 *sqrt(DIS(p[0], p[1]));else{int top;swap(p[0], p[tmp]);sort(p + 1, p + tn, cmp);s[0] = p[0];s[1] = p[1];s[2] = p[2];top = 2;for(int i = 3; i < tn; i++){while(CROSS(p[i], s[top], s[top - 1]) > 0 && top > 1)top--;s[++top] = p[i];}for(int i = 0; i < top; i++)cir +=sqrt(DIS(s[i], s[i + 1]));cir += sqrt(DIS(s[0], s[top]));}if(tx.len - cir > eps){if(ans.v > tx.v){ans = tx;fk = tx.len - cir;}else if(ans.v == tx.v && ans.cnt > tx.cnt){ans = tx;fk = tx.len - cir;}}}printf("Forest %d\nCut these trees:", ++cas);for(int i = 0; i < ans.cnt; i++)printf(" %d", ans.a[i] + 1);printf("\nExtra wood: %.2f\n", fk);}return 0;
}