题意分析

给你n棵树，每棵树都有它的坐标，价值，长度。现在要砍掉一些树，然后用这些树产生的木材（就是长度和）能够把其他的树围起来（剩下的树的凸包的周长），找到价值最小的解，如果价值相同，就选砍掉较少的树的解

解题思路

就是枚举+求凸包周长，需要有个剪纸就是如果当前的价值比当前最小价值大，那么这个情况肯定是不行的，不然会T

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<list>
using namespace std;
const double INF = 1e200;
const double EP = 1e-10;
const int maxn = 16;
const double PI = acos(-1);
struct POINT {///点 定义
    double x;
    double y;
    int v, l;
    POINT(double a = 0, double b = 0, int vv = 0, int ll = 0) { x = a; y = b; v = vv; l = ll; }
};
struct SEGMENT {///line segment///线段 定义
    POINT s;
    POINT e;
    SEGMENT(POINT a, POINT b) { s = a; e = b; }
    SEGMENT() {}
};
struct LINE {///ax + by + c = 0&&a >= 0///一般式
    double a;
    double b;
    double c;
    LINE(double da, double db, double dc) { a = da; b = db; c = dc; }
    LINE(double x1, double y1, double x2, double y2) {///根据两个点求出一般式
        a = y1 - y2; b = x2 - x1; c = x1 * y2 - x2 * y1;
        if (a < 0) { a *= -1; b *= -1; c *= -1; }
    }
};
double multiply(POINT sp, POINT ep, POINT op) {///向量op->sp X op->ep的叉乘，小于0：ep在op->sp顺时针方向//大于0：ep在op->sp逆时针方向//等于0：三点共线
    return ((sp.x - op.x) * (ep.y - op.y) - (ep.x - op.x) * (sp.y - op.y));
}
double dotmultiply(POINT p1, POINT p2, POINT p0) {
    return ((p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y));
}
bool online(SEGMENT l, POINT p) {///判断点是否在线段上
    return ((multiply(l.e, p, l.s) == 0) && (((p.x - l.s.x) * (p.x - l.e.x)) <= 0) && (((p.y - l.s.y) * (p.y - l.e.y)) <= 0));
}
bool intersect(SEGMENT u, SEGMENT v) {///两线段相交（包括端点），返回true
    return ((max(u.s.x, u.e.x) >= min(v.s.x, v.e.x)) &&
        (max(v.s.x, v.e.x) >= min(u.s.x, u.e.x)) &&
        (max(u.s.y, u.e.y) >= min(v.s.y, v.e.y)) &&
        (max(v.s.y, v.e.y) >= min(u.s.y, u.e.y)) &&
        (multiply(v.s, u.e, u.s) * multiply(u.e, v.e, u.s) >= -EP) &&
        (multiply(u.s, v.e, v.s) * multiply(v.e, u.e, v.s) >= -EP));
}
bool intersect_a(SEGMENT u, SEGMENT v) {///两线段相交（不包括端点）
    return ((intersect(u, v)) &&
        !online(u, v.s) &&
        !online(u, v.e) &&
        !online(v, u.e) &&
        !online(v, u.s));
}
int lineintersect(LINE l1, LINE l2, POINT& p) {///求两直线交点,有交点返回1和交点，没有返回0，重合返回2
    double d = l1.a * l2.b - l2.a * l1.b;
    double d2 = l1.a * l2.c - l2.a * l1.c;
    double d3 = l1.b * l2.c - l2.b * l1.c;
    if (fabs(d) < EP && fabs(d2) < EP && fabs(d3) < EP)return 2;
    p.x = (l2.c * l1.b - l1.c * l2.b) / d;
    p.y = (l2.a * l1.c - l1.a * l2.c) / d;
    if (fabs(d) < EP)return 0;
    return 1;
}
double dis(POINT a, POINT b) {///求两点距离
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
///****************凸包**************************************

int top;///凸包的顶点个数
POINT p[maxn], stack[maxn];
bool top_cmp(POINT a, POINT b) {
    double k = multiply(a, b, p[0]);
    if (k > 0)return 1;
    if (k < 0)return 0;
    return dis(a, p[0]) < dis(b, p[0]);
}
void graham(int n) {
    top = 1;
    int k = 0;
    for (int i = 1; i < n; i++)
        if (p[i].y < p[k].y || ((p[i].y == p[k].y) && (p[i].x < p[k].x)))
            k = i;
    swap(p[0], p[k]);
    sort(p + 1, p + n, top_cmp);
    stack[0] = p[0], stack[1] = p[1];
    for (int i = 2; i < n; i++) {
        while (top >= 1 && multiply(p[i], stack[top], stack[top - 1]) >= 0)top--;
        stack[++top] = p[i];
    }
}
///******************凸包结束****************
double get_area(int n, POINT v[]) {///*********多边形面积
    double ans;
    if (n < 3)return 0;
    ans = (double)(v[0].y * (v[n - 1].x - v[1].x));
    for (int i = 1; i < n; i++) {
        ans += (double)(v[i].y * (v[i - 1].x - v[i + 1].x));
    }
    return ans / 2.0;
}
double get_len(int n, POINT v[]) {
    double ans = dis(v[0], v[n - 1]);
    for (int i = 0; i < n - 1; i++) {
        ans += dis(v[i], v[i + 1]);
    }
    return ans;
}
///*********************************************************************************
POINT all[maxn];
int main() {
    //freopen("in.txt","r",stdin);
    int n;
    int cas = 1;
    while (~scanf("%d", &n)) {
        if (n == 0)break;
        for (int i = 0; i < n; i++) {
            double x, y, v, l;
            scanf("%lf%lf%lf%lf", &x, &y, &v, &l);
            all[i].x = x;
            all[i].y = y;
            all[i].v = v;
            all[i].l = l;
        }
        double min_val = 10000000;
        double min_tree = 10000;
        double num_wood = 0;
        int status = 0;
        for (int i = 1; i < (1 << n) - 1; i++) {
            int tot = 0;///the number of tree don't used
            double val = 0;
            double wood = 0;
            for (int j = 0; j < n; j++) {
                if (((1 << j) & i) == 0) {
                    p[tot++] = all[j];
                }
                else {
                    val += all[j].v;//cout<<val<<endl;
                    wood += all[j].l;
                }
            }//cout<<tot<<endl;
            if (val > min_val)continue;
            double len = 0;
            if (tot == 1)len = 0;
            else if (tot == 2)len = 2 * dis(p[0], p[1]);
            else {
                graham(tot);
                len = get_len(top + 1, stack);
            }
            if (len <= wood) {
                if (val < min_val) {
                    min_val = val;
                    min_tree = n - tot;
                    num_wood = wood - len;
                    status = i;
                }
                else if (val == min_val && min_tree > n - tot) {
                    min_tree = n - tot;
                    num_wood = wood - len;
                    status = i;
                }
            }
        }
        printf("Forest %d\nCut these trees:", cas++);
        bool used[maxn] = { 0 };
        for (int i = 0; i < n; i++) {
            if (((1 << i) & status))used[i] = 1;
        }
        for (int i = 0; i < n; i++)
            if (used[i]) {
                printf(" %d", i + 1);
            }
        printf("\nExtra wood: %.2f\n\n", num_wood + EP);
    }
    return 0;
}