POJ 1873 The Fortified Forest 凸包+枚举

题意：一个人有好多树，这些树有坐标，有价值，以及砍下这颗树能造多长的篱笆。

现在他要保护自己的树不被别人砍，就需要用篱笆把树围起来，但是需要从自己的树中砍下来几棵树造成篱笆，所以问题就来了，如何砍最少价值的树把剩余的树围起来。如果价值一样，就找砍树数量少的。

看到这道题的数据范围我就笑了，直接指数级别的枚举就行了。然后求凸包。

/*
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;
}