POJ 1873 The Fortified Forest （凸包 + 暴力枚举）

题目：传送门

题意：有 n 棵树，第 i 棵树位于点 (xi, yi)，有 vi 的价值， Li 的长度，现在你需要建一个篱笆，把所有树围起来，你只能通过砍掉其中的一些树来获得建篱笆的材料。现在问你能顺利建成篱笆需要砍掉的树的价值最小是多少，如果有多种价值一样小的方案，输出砍掉的树数目最少的情况。

2 <= n <= 15

思路：n很小，可以直接暴力枚举所有状态，如果二进制位上是1，代表砍掉这颗树。然后，剩下的树，要建篱笆将它们包围起来，且篱笆的周长要尽可能小，那就是求凸包周长了。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
#define LL long long
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF INT_MAX
#define inf LLONG_MAX
#define PI acos(-1)
using namespace std;

const int N = 5e4 + 5;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) { } /// 构造函数
};

typedef Point Vector;
/// 向量+向量=向量， 点+向量=向量
Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
///点-点=向量
Vector operator - (Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }
///向量*数=向量
Vector operator * (Vector A, double p) { return Vector(A.x * p, A.y * p); }
///向量/数=向量
Vector operator / (Vector A, double p) { return Vector(A.x / p, A.y / p); }

const double eps = 1e-10;
int dcmp(double x) {
    if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
}

bool operator < (const Point& a, const Point& b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

bool operator == (const Point& a, const Point &b) {
    return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; } /// 点积
double Length(Vector A) { return sqrt(Dot(A, A)); } /// 计算向量长度
double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); } /// 向量A、B夹角
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } /// 叉积

struct note {
    Point p;
    int V, L;
}a[N];

Point P[N], Q[N];

int ConvexHull(Point* p, int n, Point* ch) { /// 求凸包
    sort(p, p + n);
    int m = 0;
    rep(i, 0, n - 1) {
        while(m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    dep(i, 0, n - 2) {
        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;
}

int ANS[N];

int main() {

    int n; int Cas = 0;
    while(scanf("%d", &n) && n) {

        rep(i, 0, n - 1) scanf("%lf %lf %d %d", &a[i].p.x, &a[i].p.y, &a[i].V, &a[i].L);

        int ans_val = 10000000, ans_num = 0;
        double ans_dis = 0.0;

        rep(i, 0, (1 << n) - 1) { /// 暴力枚举

            int tmp_val = 0, tmp_num = 0;
            double tmp_dis = 0;

            rep(j, 0, n - 1) {
                if((i >> j) & 1) tmp_dis += a[j].L, tmp_val += a[j].V;
                else P[tmp_num++] = a[j].p;
            }

            tmp_num = ConvexHull(P, tmp_num, Q);

            double need_dis = 0.0;
            rep(j, 0, tmp_num - 1) {
                need_dis += Length(Q[(j + 1) % tmp_num] - Q[j]);
            }

            if(dcmp(tmp_dis - need_dis) >= 0) {
                if(tmp_val < ans_val) {
                    ans_val = tmp_val;
                    ans_num = 0;
                    rep(j, 0, n - 1) {
                        if((i >> j) & 1) ANS[ans_num++] = j + 1;
                    }
                    ans_dis = tmp_dis - need_dis;
                }
                else if(tmp_val == ans_val) {
                    if(tmp_num < ans_num) {
                        rep(j, 0, n - 1) {
                            if((i >> j) & 1) ANS[ans_num++] = j + 1;
                        }
                        ans_dis = tmp_dis - need_dis;
                    }
                }
            }

        }

        printf("Forest %d
", ++Cas);
        printf("Cut these trees:");
        rep(i, 0, ans_num - 1) printf(" %d", ANS[i]); puts("");
        printf("Extra wood: %.2f
", ans_dis);
        puts("");
    }

    return 0;
}