UVA 811 The Fortified Forest (凸包 + 状态压缩枚举)
题目链接:UVA 811 Description
Input
Output
Sample Input6 0 0 8 3 1 4 3 2 2 1 7 1 4 1 2 3 3 5 4 6 2 3 9 8 3 3 0 10 2 5 5 20 25 7 -3 30 32 0 Sample OutputForest 1 Cut these trees: 2 4 5 Extra wood: 3.16 Forest 2 Cut these trees: 2 Extra wood: 15.00 Solution题意有 (n) 颗树,每颗树的坐标为 (x,y) ,价值为 (v_i) 长度为 (l_i)。现在要用篱笆将其中一些树围起来,但篱笆制作来源于这些树,即要求砍掉的树能构成篱笆的长度 (>=) 剩余树的凸包周长。现在要使得砍掉树的价值之和最小,问需要砍掉哪些树(如果有价值相同的解,就输出砍的树最少的解)。 题解凸包周长 状态压缩枚举 树的规模比较小,用二进制枚举所有情况即可。 Code#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using namespace std; const double eps = 1e-8; const int inf = 0x3f3f3f3f; const int maxn = 15 + 10; int n; struct Point { double x,y; double v,l; int id; Point() {} Point(double a,double b) : x(a),y(b) {} bool operator<(const Point &b) const { if (x < b.x) return 1; if (x > b.x) return 0; return y < b.y; } Point operator-(const Point &b) { return Point(x - b.x,y - b.y); } } p[maxn],stk[maxn],tmp[maxn]; typedef Point Vec; int sgn(double x) { if (fabs(x) <= eps) return 0; return x > 0 ? 1 : -1; } double dist(Point a,Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } double cross(Vec a,Vec b) { return a.x * b.y - a.y * b.x; } int Andrew(int l) { int len = 0; for (int i = 1; i <= l; ++i) { while (len > 1 && sgn(cross(stk[len] - stk[len - 1],tmp[i] - stk[len - 1])) == -1) { len--; } stk[++len] = tmp[i]; } int k = len; for (int i = l - 1; i >= 1; --i) { while (len > k && sgn(cross(stk[len] - stk[len - 1],tmp[i] - stk[len - 1])) == -1) { len--; } stk[++len] = tmp[i]; } return len; } int main() { int kase = 0; while(cin >> n && n) { if(kase) printf("n"); // 最后一行不输出空行,WA了好几次 for (int i = 1; i <= n; ++i) { scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].v,&p[i].l); p[i].id = i; } sort(p + 1,p + 1 + n); double min_val = 1e8; double min_len; int min_num = inf; int min_state; int N = 1 << n; for(int i = 1; i < N; ++i) { double cur_len = 0; double cur_val = 0; int cur_num = 0; for(int j = 0; j < n; ++j) { if(!((i) & (1<<j)) ) { cur_val += p[j + 1].v; cur_len += p[j + 1].l; } else { tmp[++cur_num] = p[j + 1]; } } int t = Andrew(cur_num); double d = 0; for(int j = 1; j < t; ++j) { d += dist(stk[j],stk[j + 1]); } if(sgn(cur_len - d) >= 0) { if(sgn(min_val - cur_val) > 0 || (sgn(min_val - cur_val) == 0 && min_num > cur_num)) { min_val = cur_val; min_num = cur_num; min_state = i; min_len = cur_len - d; } } } printf("Forest %dnCut these trees: ",++kase); vector<int> id; for(int i = 0; i < n; ++i) { if((~min_state) & (1 << i)) { id.push_back(p[i + 1].id); } } sort(id.begin(),id.end()); for(int i = 0; i < id.size(); ++i) { printf("%d",id[i]); printf("%s",i == id.size() - 1? "n": " "); } printf("Extra wood: %.2lfn",min_len); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |