学步园

题目来源:http://acm.fzu.edu.cn/problem.php?pid=1515福州大学OJ15

       题目大意,有一个立方体的盒子,给出对角两个顶点的坐标,在这个盒子里,有N个点,其中N<=6.在其中任何一个点上放上气球,该气球自动膨胀直到碰到盒壁或其它气球,必须等一个气球扩展完毕才能扩展第二个气球,按照怎样的顺序在这N个点上放上气球,才能使气球的总体积最大,题目要求输出剩余体积,四舍五入取整.

       因为只有6个气球,全排列共有6!=720种膨胀方案.因为情况较少,很容易想到枚举.用DFS求出每种膨胀方案的顺序,然后再依次求得每个气球到6个面以及其它气球的距离,取其中的最小值作为半径.有一个要注意的地方就是如果某点没有气球,是可以被包含在别的气球内部的,显然,这时候该点气球所占的体积为0,一开始没有考虑到这个问题,WA了两次...上代码..

import java.util.Arrays;<br /> import java.util.Scanner;<br /> public class Main{<br /> public static void main(String []args){<br /> new Main();<br /> }<br /> int total;<br /> int[] visit;<br /> int[] result;<br /> double max;<br /> Point c1,c2,ps[];<br /> int count=0;<br /> public Main(){<br /> Scanner sc=new Scanner(System.in);<br /> while(sc.hasNext()){<br /> total=sc.nextInt();<br /> c1=new Point(sc.nextDouble(),sc.nextDouble(),sc.nextDouble());//盒子的两个对角坐标<br /> c2=new Point(sc.nextDouble(),sc.nextDouble(),sc.nextDouble());<br /> ps=new Point[total];//气球的坐标<br /> for(int i=0;i<total;i++){<br /> ps[i]=new Point(sc.nextDouble(),sc.nextDouble(),sc.nextDouble());<br /> }<br /> //枚举气球膨胀的顺序;<br /> visit=new int[total];<br /> Arrays.fill(visit, 0);<br /> result=new int[total];<br /> max=0;<br /> dfs(0);//全排列total个数,结果放入result中<br /> double v=Math.abs((c1.x-c2.x)*(c1.y-c2.y)*(c1.z-c2.z));<br /> System.out.printf("%.0f",v-max);//输出最小的剩余面积<br /> System.out.println();<br /> }<br /> }<br /> private void dfs(int count) {<br /> for(int i=0;i<total;i++){<br /> if(visit[i]==0){<br /> visit[i]=1;<br /> result[count]=i;<br /> if(count==total-1){<br /> cal();//全排列到最后一个数时计算当前的面积<br /> }else{<br /> dfs(count+1);<br /> }<br /> visit[i]=0;<br /> }<br /> }<br /> }<br /> private void cal() {<br /> double totalv=0;//所有圆的面积和<br /> for(int i=0;i<total;i++){<br /> ps[i].r=0;<br /> }<br /> for(int i=0;i<total;i++){<br /> int now=result[i];<br /> //到面的最短距离<br /> double x1=Math.min(Math.abs(ps[now].x-c1.x),Math.abs(ps[now].x-c2.x));<br /> double x2=Math.min(Math.abs(ps[now].y-c1.y),Math.abs(ps[now].y-c2.y));<br /> double x3=Math.min(Math.abs(ps[now].z-c1.z),Math.abs(ps[now].z-c2.z));<br /> ps[now].r=Math.min(x1,Math.min(x2, x3));<br /> //到其它点的距离<br /> for(int j=0;j<total;j++){<br /> if(now==j||ps[j].r==0)continue;//注意,可以将其它点包含于圆内<br /> double x4=Math.sqrt((ps[now].x-ps[j].x)*(ps[now].x-ps[j].x)+(ps[now].y-ps[j].y)*(ps[now].y-ps[j].y)+(ps[now].z-ps[j].z)*(ps[now].z-ps[j].z))-ps[j].r;<br /> //当点在该圆外时,半径等于到边和到该圆的距离的较小值<br /> ps[now].r=Math.min(ps[now].r, x4);<br /> //如果点在该圆内,半径置为0<br /> if(ps[now].r<0)ps[now].r=0;<br /> }<br /> totalv+=4.0d/3.0d*Math.PI*ps[now].r*ps[now].r*ps[now].r;<br /> }<br /> if(totalv>max)max=totalv;<br /> }<br /> }<br /> class Point{<br /> double x,y,z;//坐标<br /> double r;//半径<br /> public Point(double x,double y,double z){<br /> this.x=x;this.y=y;this.z=z;<br /> }<br /> }