poj - 1873 - The Fortified Forest

 題意：給出n棵樹的坐標，樹的高度和樹的價值，從這些樹中砍掉一些（整棵整棵的）做圍欄把剩余的樹圍起來，使得消耗的樹的價值最小。輸出應砍掉哪裡些樹以及剩余的材料的長度。（如果砍掉的價值相同，則取砍掉數目少的）(2 <= n <= 15)

——>>用二進制映射枚舉每種砍樹的情況，對於每一種情況，求凸包，求凸包的周長，判斷。(這裡用G++提交)

注意：1、如果砍掉的價值相同，數目也相同，應砍編號小的樹；

2、最後輸出時用"%.2f"，千萬別用"%.2lf"，多一個l與少一個l區別大大的大！！！

#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;
}