本文主要是介绍poj 1873 The Fortified Forest (位运算枚举 + 凸包周长)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=1873
大意：有一片N棵树的森林，要从中砍掉几棵树做成篱笆，把剩下的树围起来
输入：给N课树，每棵树的坐标是x,y，每棵树有一个vi和li分别代表砍掉这棵树的花费和砍掉后可做成篱笆的长度
输出：被砍掉树的编号（从1开始）、把剩下的树围起来后剩下的篱笆米数。
思路：暴力枚举..用01表示哪些树被砍了，维护一个可行的最小值，坑点是如果用%.2lf输出会wa，不知道是不是出现-0.00的原因，用%.2f过了，代码如下，欢迎指正：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <stack>
#define INF 0x3fffffff
using namespace std;
struct point{int x,y;int vi,li;
}p0,p[16];int cross(int x1,int y1,int x2,int y2){return x2*y1 - x1*y2;
}
double dis(const point &a,const point &b){return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool cmp(const point &a,const point &b){int x1 = a.x - p0.x,y1 = a.y - p0.y;int x2 = b.x - p0.x,y2 = b.y - p0.y;if(cross(x1,y1,x2,y2) != 0)return cross(x1,y1,x2,y2) < 0;elsereturn dis(a,p0) < dis(b,p0);
}
//判断左旋还是右旋
bool ok(point p1,point p2,point p3){int x1 = p2.x - p1.x;int y1 = p2.y - p1.y;int x2 = p3.x - p2.x;int y2 = p3.y - p2.y;int c = cross(x1,y1,x2,y2);if(c <= 0) return true;else return false;
}
//计算周长
double GrahamScan(point px[],int N){//当森林中只有一颗或两棵树的时候if(N == 1) return 0;else if(N==2) return 2*dis(px[0],px[1]);//否则进行进行凸包计算求周长//凸包计算的方法推荐《算法艺术与信息学竞赛》（黑书）上P391页的相关介绍p0 = px[0];sort(px+1,px+N,cmp);stack<point> s;s.push(px[0]);s.push(px[1]);int i = 2;while(i < N ){point p2 = s.top();s.pop();point p1 = s.top();point p3 = px[i];if(ok(p1,p2,p3)){s.push(p2);s.push(px[i]);i++;}}//其实这里在上面可以写成N-1把最后一个点不进栈的。s.pop();double C = 0.0;point now = px[N-1];while(!s.empty()){C += dis(now,s.top());now = s.top();s.pop();}C += dis(px[0],px[N-1]);return C;
}
int main()
{int n,cas = 1;while(~scanf("%d",&n)&&n){for(int i=0;i<n;i++)scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].vi,&p[i].li);int N = 1 << n;int ans_value = INF;int ans_cnt = 0;int ans_cutTrees[15];double ans_extra = 0.0;for(int bit=0;bit<N;bit++){int tmp_value = 0;double tmp_li = 0;int tmp_CutTrees[15],tmp_cnt = 0,not_cnt = 0;point notCut[15];for(int i =0;i<n;i++){// the trees have been cut downif(bit & (1 << i)){tmp_value += p[i].vi;tmp_li += (p[i].li*1.0);tmp_CutTrees[tmp_cnt++] = i;}else{//将最下、最右的点放在px[0]，方便计算凸包if(notCut == 0){notCut[not_cnt++] = p[i];}else if(p[i].y < notCut[0].y || (p[i].y == notCut[0].y&&p[i].x < notCut[0].x)){notCut[not_cnt++] = notCut[0];notCut[0] = p[i];}else {notCut[not_cnt++] = p[i];}}}if((tmp_value >= ans_value && ans_cnt <= tmp_cnt)|| tmp_value > ans_value) continue;double C = GrahamScan(notCut,not_cnt);if(C <= tmp_li){ans_value = tmp_value;ans_extra = tmp_li - C;ans_cnt = tmp_cnt;for(int i = 0;i<ans_cnt;i++)ans_cutTrees[i] = tmp_CutTrees[i];}}printf("Forest %d\n",cas++);printf("Cut these trees:");for(int i =0;i<ans_cnt;i++) printf(" %d",ans_cutTrees[i]+1);printf("\n");printf("Extra wood: %.2f\n\n",ans_extra);}return 0;
}
这篇关于poj 1873 The Fortified Forest (位运算枚举 + 凸包周长)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
