企业官网建设流程全解析

题目描述

国王拥有一片珍贵树林，需要砍伐其中一些树木，用其木材建造围栏，将剩余树木围住。每棵树有坐标(xi,yi)(x_i, y_i)(xi​,yi​)、价值viv_ivi​和可提供的围栏长度lil_ili​。要求选择一个砍伐集合，使得剩余树木能被围栏围住，且砍伐树木的总价值最小；若有多个最小价值方案，选择砍伐树木数量最少的。输出需要砍伐的树木编号，以及剩余木材长度（即总可提供围栏长度减去凸包周长）。树木视为点，直径为零。

输入格式

输入包含多个测试用例。每个测试用例第一行为整数nnn（2≤n≤152 \le n \le 152≤n≤15）。随后nnn行，每行四个整数xi,yi,vi,lix_i, y_i, v_i, l_ixi​,yi​,vi​,li​，描述一棵树。输入以n=0n = 0n=0结束。

输出格式

对于每个测试用例，输出格式为：

Forest k Cut these trees: id1 id2 ... Extra wood: length

其中lengthlengthlength精确到两位小数。不同测试用例输出之间用一个空行分隔。

样例输入

6 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

样例输出

Forest 1 Cut these trees: 2 4 5 Extra wood: 3.16 Forest 2 Cut these trees: 2 Extra wood: 15.00

题目分析

n≤15n \le 15n≤15，因此可枚举所有2n2^n2n个砍伐子集。对于每个子集，检查剩余树木是否可用该子集提供的木材围住，即剩余树木的凸包周长是否不超过砍伐树木提供的总木材长度。若满足，则记录总价值和砍伐数量，按总价值优先、砍伐数量次优选择最小方案。凸包使用Graham\texttt{Graham}Graham扫描算法计算。

解题思路

实现步骤确定如下：

步骤1\texttt{1}1. 读入nnn，存储所有树的信息。

步骤2\texttt{2}2. 使用深度优先搜索（DFS\texttt{DFS}DFS）枚举所有砍伐子集。递归函数dfs(value,length,depth)\texttt{dfs}(value, length, depth)dfs(value,length,depth)参数为当前已选砍伐树的总价值、总木材长度和已处理树的数量，用于剪枝。若当前总价值已大于当前最优值，则返回。

步骤3\texttt{3}3. 对于每个候选砍伐树iii，标记为砍伐，并计算剩余树的凸包周长。若剩余树数k≤2k \le 2k≤2，则凸包周长为000（因为两点或一点无需围栏，或视为周长000）。否则，调用grahamConvexHull\texttt{grahamConvexHull}grahamConvexHull计算凸包周长。

步骤4\texttt{4}4. 若当前总木材长度length+lilength + l_ilength+li​大于凸包周长（考虑浮点误差），则此方案可行。更新最优值、最优砍伐标记和剩余木材长度。

步骤5\texttt{5}5. 递归继续枚举。回溯时取消砍伐标记。

步骤6\texttt{6}6. 所有枚举结束后，按格式输出结果。

凸包算法注意处理共线点，以及点数小于333时的特殊情况。

代码实现

// The Fortified Forest// UVa ID: 811// Verdict: Accepted// Submission Date: 2016-12-15// UVa Run Time: 0.080s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXV=20;constintEPSILON=1E-6;structpoint{intx,y,v,l;booloperator<(constpoint&another)const{if(abs(x-another.x)>0)returnx<another.x;elsereturny<another.y;}booloperator==(constpoint&another)const{returnabs(x-another.x)<=0&&abs(y-another.y)<=0;}};structpolygon{intnumber;point vertex[MAXV];doubledistanceOfPoints(point a,point b){returnsqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));}doublecircumference(){doublelength=0.0;for(inti=0;i<number;i++)length+=distanceOfPoints(vertex[i],vertex[(i+1)%number]);returnlength;}};point lowerLeftPoint,allPoints[20];intn,minValue,cutted[20],best[20];doubleextraWood;// 叉积。intcp(point a,point b,point c){return(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}// 从点a向点b望去，点c位于线段ab的右侧，返回true。boolcw(point a,point b,point c){returncp(a,b,c)<0;}// 从点a向点b望去，点c位于线段ab的左侧时，返回true。boolccw(point a,point b,point c){returncp(a,b,c)>0;}// 当三点共线时，返回true。boolcollinear(point a,point b,point c){returnfabs(cp(a,b,c))==0;}// 判断是否向左转或共线。boolccwOrCollinear(point a,point b,point c){returncp(a,b,c)>=0;}// 两点距离的平方值。doubledistanceToLowerLeftPoint(point p){returnpow(lowerLeftPoint.x-p.x,2)+pow(lowerLeftPoint.y-p.y,2);}// 按相对于参考点的极角大小进行排序。boolsmallerAngle(point first,point second){if(collinear(lowerLeftPoint,first,second))returndistanceToLowerLeftPoint(first)<=distanceToLowerLeftPoint(second);returnccw(lowerLeftPoint,first,second);}// Graham凸包扫描算法。polygongrahamConvexHull(point vertex[],intnumber){polygon pg;// 点数小于等于3个，认为所有的点均在凸包上。if(number<=3){for(inti=0;i<number;i++)pg.vertex[i]=vertex[i];pg.number=number;returnpg;}// 按横坐标和纵坐标排序，移除重复点。sort(vertex,vertex+number);number=unique(vertex,vertex+number)-vertex;// 按极角排序。lowerLeftPoint=vertex[0];sort(vertex+1,vertex+number,smallerAngle);// 将初始的两点放入凸包。pg.vertex[0]=vertex[0];pg.vertex[1]=vertex[1];// 设置哨兵元素，将最左最低点设置为最后一个元素以便扫描时能回到参考点。vertex[number]=lowerLeftPoint;inti=2,top=1;while(i<=number){if(cw(pg.vertex[top-1],pg.vertex[top],vertex[i]))top--;elseif(collinear(pg.vertex[top-1],pg.vertex[top],vertex[i]))pg.vertex[top]=vertex[i++];elsepg.vertex[++top]=vertex[i++];}pg.number=top;returnpg;}point uncuttedTrees[20];voiddfs(intvalue,intlength,intdepth){if(value>minValue||depth>=n)return;for(inti=0;i<n;i++){if(!cutted[i]){cutted[i]=1;intk=0;for(intj=0;j<n;j++)if(!cutted[j])uncuttedTrees[k++]=allPoints[j];polygon pg=grahamConvexHull(uncuttedTrees,k);if((double)(length+allPoints[i].l)>pg.circumference()+EPSILON){if(value+allPoints[i].v<minValue){minValue=value+allPoints[i].v;extraWood=(double)(length+allPoints[i].l)-pg.circumference();memcpy(best,cutted,sizeof(cutted));}}dfs(value+allPoints[i].v,length+allPoints[i].l,depth+1);cutted[i]=0;}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0;while(cin>>n,n>0){for(inti=0;i<n;i++)cin>>allPoints[i].x>>allPoints[i].y>>allPoints[i].v>>allPoints[i].l;minValue=10000000;memset(cutted,0,sizeof(cutted));dfs(0,0,0);if(cases>0)cout<<'\n';cout<<"Forest "<<++cases<<'\n';cout<<"Cut these trees:";for(inti=0;i<n;i++)if(best[i])cout<<' '<<(i+1);cout<<'\n';cout<<"Extra wood: "<<fixed<<setprecision(2)<<extraWood<<'\n';}return0;}

总结

本题通过枚举所有砍伐子集，结合凸包算法判断剩余树木是否能被围住，并在搜索中剪枝优化。由于n≤15n \le 15n≤15，2n2^n2n枚举可行。凸包使用Graham\texttt{Graham}Graham扫描，注意处理共线点和点数较少的情况。输出需按指定格式，不同测试用例间空行。该解法清晰且高效，是枚举与几何计算结合的典型问题。