Balloons in a Box

2019-04-14 15:49发布

站内文章 / 模拟电子
12974 0 1439
问题描述
　　你要写一个程序，使得能够模拟在长方体的盒子里放置球形的气球。
　　接下来是模拟的方案。假设你已知一个长方体的盒子和一个点集。每一个点代表一个可以放置气球的位置。在一个点上放置一个气球，就是以这个点为球心，然后让这个球膨胀，直到触及盒子的边缘或者一个之前已经被放置好的气球。你不能使用一个在盒子外面或者在一个之前已经放置好的气球里面的点。但是，你可以按你喜欢的任意顺序使用这些点，而且你不需要每个点都用。你的目标是按照某种顺序在盒子里放置气球，使得气球占据的总体积最大。
　　你要做的是计算盒子里没被气球占据的体积。
输入格式
　　第一行包含一个整数n表示集合里点的个数（1≤n≤6）。第二行包含三个整数表示盒子的一个角落的(x,y,z)坐标，第三行包含与之相对的那个角落的(x,y,z)坐标。接下来n行，每行包含三个整数，表示集合中每个点的(x,y,z)坐标。这个盒子的每维的长度都是非零的，而且它的边与坐标轴平行。
输出格式
　　只有一行，为那个盒子没被气球占据的最小体积（四舍五入到整数）。
样例输入
2
0 0 0
10 10 10
3 3 3
7 7 7
样例输出
774
数据规模和约定
　　所有坐标的绝对值小于等于1000
　　对于20%的数据：n=1
　　对于50%的数据：1≤n≤3
　　对于100%的数据：1≤n≤6 这题在蓝桥杯oj做的，好像是某一年的worldfinal题目。
虽然不难，但是涉及到的知识点比较多。有排列、组合、几何。基础掌握好了之后直接dfs就完事了。 #include using namespace std; #include #include #define maxn 10 #define pi 3.14159265358 double ans=-1; double tmp=0; int x1,x2,y_1,y2,z1,z2; struct point { int x,y,z; double r;//实际半径 double v; double diswall; point(){ x=y=z=r=v=0; diswall=0; } getdiswall(){ double t1 = min(abs(x - x1), abs(x - x2)); double t2 = min(abs(y - y_1),abs(y - y2)); double t3 = min(abs(z - z1),abs(z - z2)); double r = min(t1, t2); r = min(r, t3); diswall=r; } double getv(){ v=4.0/3.0*pi*r*r*r;//这个地方要是写4/3就得出1了 //cout<<"r"< return v; } }p[maxn]; int vis[maxn];//组合队伍访问情况 int now[maxn];//组合队伍 int nown;//组合队伍元素数 int arr[maxn];//排列队伍 double dis(int i,int j){ double xd=(p[arr[i]].x-p[arr[j]].x); double yd=(p[arr[i]].y-p[arr[j]].y); double zd=(p[arr[i]].z-p[arr[j]].z); return sqrt(xd*xd+yd*yd+zd*zd); } int inbox(int x,int y,int z){ if(x<max(x1,x2)&&x>min(x1,x2)&&y<max(y_1,y2)&&y>min(y_1,y2)&&z<max(z1,z2)&&z>min(z1,z2)) return 1; return 0; } //排列结束后由arr得出体积 //arr存放的是nown个有顺序的点 double fun(){ double ft=0; for(int i=0;i<nown;i++){ //在i点放一个球 看点是否在立方体内 if(!inbox(p[arr[i]].x,p[arr[i]].y,p[arr[i]].z)) continue; //看这个点是否已经被其他球包含 int k=0; for(;k<i;k++){ double disball=dis(i,k); if(disball<=p[arr[k]].r) break; } if(k<i){ p[arr[i]].r=0; continue; } //计算这个点放球带来的收益 double minr=p[arr[i]].diswall; for(int j=0;j<i;j++){ double disball=dis(i,j); minr=min(minr,disball-p[arr[j]].r); } p[arr[i]].r=minr; ft+=p[arr[i]].getv(); } return ft; } void dfs(int i){ if(i>=nown){ for(int j=0;j<nown;j++) p[arr[j]].r=0; tmp=fun(); ans=max(ans,tmp); return; } for(int j=0;j<nown;j++){ if(!vis[j]){ vis[j]=1; arr[i]=now[j]; dfs(i+1); vis[j]=0; } } } int main() { //freopen("in.txt","r",stdin); int n; cin>>n; cin>>x1>>y_1>>z1; cin>>x2>>y2>>z2; for(int i=0;i<n;i++){ cin>>p[i].x>>p[i].y>>p[i].z; p[i].getdiswall(); } int m=1<<n; int s; for(int i=0;i<m;i++){ nown=0; for(int j=0;j<n;j++) { s=1<<j; if(s & i)//第j个点进入组合 now[nown++]=j; } //对组合进行全排列 dfs(0); } double v=abs(z1-z2)*abs(y_1-y2)*abs(x1-x2); printf("%.0f",round(v-ans)); } 这题结果要求四舍五入一开始没注意到，或者没理解透，提交了好几次都是直接用long long取整的
一开始样写的 cout<<v-(long long)ans<<endl; 导致一直有一半数据没过去
后来注意到了四舍五入用了 printf("%.0f",v-ans); 居然过了（蓝桥的数据果然水啊233），但是后来查资料知道printf()某些时候具有四舍五入的功能，但是并不稳定。 float x; while(scanf("%f",&x)!=EOF) { printf("%f ",x); printf("%.0f ",x); } 2.500000 2 2.400000 2 2.600000 3 最正确的做法应该是用上round函数 printf("%.0f",round(v-ans)); 开始一直以为错误在其他地方，导致浪费了一些时间。结果居然错在输出上。基础真的是非常重要啊。

热门文章