此题大意是有n棵树(n < 15)，每棵树都有坐标，可形成的木材长度，价值。
求砍掉一些树，这些树的价值尽可能小，使得剩余的树可以用木材围成一个凸包。
并求剩余木材的长度

解法： 枚举所有状态，判断一下能否形成凸包，是否解更优即可。。
注意： 此题有一个剪枝，若当前的枚举状态，砍树价值已经大于得到的最优状态，continue即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 17;
const double EPS = 1e-6;
const int INF = 0x7fffffff;
struct Point
{
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    double getDis(Point rhs)
    {
        double xx = rhs.x - x;
        double yy = rhs.y - y;
        return sqrt(xx * xx + yy * yy);
    }
    void input()
    {
        scanf("%lf%lf", &x, &y);
    }

    bool operator <(Point &rhs)
    {
        if(fabs(y - rhs.y) <= EPS) return x < rhs.x;
        return y < rhs.y;
    }
    double x, y;
    double v, l;
    int id;
};
Point operator -(Point lhs, Point rhs){return Point(rhs.x - lhs.x, rhs.y - lhs.y);}
double operator ^(Point lhs, Point rhs){return lhs.x * rhs.y - lhs.y * rhs.x;}

Point point[MAXN];
Point src;
int n;

bool cmp(Point &a, Point &b)
{
    double temp = (a - src) ^ (b - src);
    if(fabs(temp) <= EPS) return a.getDis(src) < b.getDis(src);
    return temp > 0;
}

int stack[MAXN];
void getConvex(vector<Point> &a, vector<Point> &out)
{
    out.clear();
    sort(a.begin(), a.end(), cmp);

    stack[0] = 0;
    stack[1] = 1;
    int top = 1;
    for(int i = 2; i < (int)a.size(); ++i)
    {
        while(top >= 1 && ((a[i] - a[stack[top - 1]]) ^ (a[stack[top]] - a[stack[top - 1]])) >= 0)
        {
            --top;
        }
        stack[++top] = i;
    }
    for(int i = 0; i <= top; ++i) out.push_back(a[stack[i]]);
}

vector<Point> selected;
vector<Point> cut;
vector<Point> ans;
vector<Point> convex;
double extraLength;

void solve()
{
    int MAXBOUND = 1 << n;
    double maxL, curL, curV;
    double bestV = INF;
    bool fst;
    for(int i = 0; i < MAXBOUND; ++i)
    {
        selected.clear();
        cut.clear();
        maxL = curL = curV = 0.0;
        fst = true;
        for(int j = 1; j <= n; ++j)
        {
            int bit = 1 << (j - 1);
            if(bit & i)
            {
                selected.push_back(point[j]);
                if(fst)
                {
                    fst = false;
                    src = point[j];
                }
                else
                {
                    if(point[j] < src) src = point[j];
                }
            }
            else
            {
                cut.push_back(point[j]);
                curV += point[j].v;
                maxL += point[j].l;
            }
        }
        if(selected.size() >= 3)
        {
            if(curV > bestV + EPS) continue;// 剪枝神了！！
            getConvex(selected, convex);
            for(int i = 0; i < (int)convex.size(); ++i)
            {
                // printf("%d ", convex[i].id);
                int nxt = (i + 1) % convex.size();
                curL += convex[i].getDis(convex[nxt]);
            }
            // putchar('\t');
            // if(curL <= maxL)printf("value: %.2lf\n", curV);
            // else putchar('\n');
        }
        else if(selected.size() == 2)
        {
            curL = 2.0 * selected[0].getDis(selected[1]);
        }
        else if(selected.size() == 1)
        {
            curL = 0;
        }

        if(curL <= maxL)
        {
            if(fabs(curV - bestV) <= EPS)
            {
                if(cut.size() < ans.size())
                {
                    ans = cut;
                    extraLength = maxL - curL;
                }
            }
            else if(curV < bestV)
            {
                bestV = curV;
                ans = cut;
                extraLength = maxL - curL;
            }
        }
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    int tcase = 0;
    while(scanf("%d", &n) && n != 0)
    {
        if(tcase) putchar('\n');
        ++tcase;

        for(int i = 1; i <= n; ++i)
        {
            scanf("%lf%lf%lf%lf", &point[i].x, &point[i].y, &point[i].v, &point[i].l);
            point[i].id = i;
        }
        solve();
        printf("Forest %d\n", tcase);
        printf("Cut these trees:");
        for(int i = 0; i < (int)ans.size(); ++i)
        {
            printf(" %d", ans[i].id);
        }
        printf("\nExtra wood: %.2lf\n", extraLength);
    }
}