`

盒子里的气球

 
阅读更多

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/*
 * Problem Description
 You must write a program that simulates placing spherical balloons into a rectangular box.
 The simulation scenario is as follows. Imagine that you are given a rectangular box and a set of points inside the box. Each point represents a position where you might place a balloon. To place a balloon at a point, center it at the point and inflate the balloon until it touches a side of the box or a previously placed balloon. You may use the points in any order you like, and need not use every point. Your objective is to place balloons in the box in an order that maximizes the total volume occupied by the balloons.
 You are required to calculate the volume within the box that is not enclosed by the balloons.
 All integer will be in [-1000, 1000].
 Input
 The input consists of several test cases. The first line of each test case contains a single integer n that indicates the number of points in the set (n ≤ 6). The second line contains three integers that represent the (x, y, z) integer coordinates of a corner of the box, and the third line contains the (x, y, z) integer coordinates of the opposite corner of the box. The next n lines of the test case contain three integers each, representing the (x, y, z) coordinates of the points in the set. The box has non-zero length in each dimension and its sides are parallel to the coordinate axes.
 Output
 For each test case print one line which indicates the volume of the box not occupied by balloons. Round the volume to the nearest integer.
 Sample Input
 2
 0 0 0
 10 10 10
 3 3 3
 7 7 7

 Sample Output
 774
 */
public class Balloons {
	private int N;
	private Balloon lefttop;
	private Balloon rightbottom;
	private Balloon[] balloons; 
	List<List> seq = new ArrayList<List>();
	
	/**
	 * @param n
	 * @param lefttop
	 * @param rightbottom
	 */
	public Balloons(int n, Balloon lefttop, Balloon rightbottom) {
		super();
		N = n;
		this.lefttop = lefttop;
		this.rightbottom = rightbottom;
	}


	public double getMaxBallV() {
		double v = 0;
		sort(Arrays.asList(balloons), new ArrayList());
		for(List t : seq) {
			double av = 0;
			for(int i=0;i<t.size();i++) {
				double r = minr(i);
				balloons[i].setR(r);
				av = av + (4.0/3.0)*Math.PI*balloons[i].getR()*balloons[i].getR()*balloons[i].getR();
			}
			if(av > v) {
				v = av;
			}
		}
		return v;
	}

    private void sort(List datas, List target) {  
        if (target.size() == N) {  
            seq.add(target); 
            return;  
        }  
        for (int i = 0; i < datas.size(); i++) {  
            List newDatas = new ArrayList(datas);  
            List newTarget = new ArrayList(target);  
            newTarget.add(newDatas.get(i));  
            newDatas.remove(i);  
            sort(newDatas, newTarget);  
        }  
    }
	private double minr(int i) {
		int[] mi = new int[6];
		mi[0] = Math.abs(balloons[i].getX() -lefttop.getX()) ;
		mi[1] = Math.abs(balloons[i].getY() -lefttop.getY()) ;
		mi[2] = Math.abs(balloons[i].getZ() -lefttop.getZ()) ;
		mi[3] = Math.abs(balloons[i].getX() -rightbottom.getX()) ;
		mi[4] = Math.abs(balloons[i].getY() -rightbottom.getY()) ;
		mi[5] = Math.abs(balloons[i].getZ() -rightbottom.getZ()) ;
		double m = Double.MAX_VALUE;
		for(int j=0;j<6;j++ ) {
		  if(mi[j]<m) {
		         m=mi[j];
		  }
		 }
		for(int j=0;j<N;j++) {
			if(i!=j){
				m = Math.min(m, distant(i, j)-balloons[j].getR());
			}
		}
		return m;
	}


	private double distant(int i, int j) {
		return  Math.round(Math.sqrt((balloons[i].getX()-balloons[j].getX())*(balloons[i].getX()-balloons[j].getX()) + 
		(balloons[i].getY()-balloons[j].getY())*(balloons[i].getY()-balloons[j].getY())+
		(balloons[i].getZ()-balloons[j].getZ())*(balloons[i].getZ()-balloons[j].getZ())));
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String str = "2.0 0 0.10 10 10.3 3 3.7 7 7";
		Scanner scanner = new Scanner(str);
		scanner.useDelimiter("\\.");
		int n = scanner.nextInt();
		String[] s = scanner.next().split(" ");
		Balloon lefttop = new Balloon(Integer.parseInt(s[0]),Integer.parseInt(s[1]),Integer.parseInt(s[2]),0);
		String[] s1 = scanner.next().split(" ");
		Balloon rightbottom = new Balloon(Integer.parseInt(s1[0]),Integer.parseInt(s1[1]),Integer.parseInt(s1[2]),0);
		Balloon[] ballons = new Balloon[n];
		for(int i = 0;i<n;i++){
			String[] s0 = scanner.next().split(" ");;
			ballons[i] = new Balloon(Integer.parseInt(s0[0]),Integer.parseInt(s0[1]),Integer.parseInt(s0[2]),0);
		}
		Balloons b = new Balloons(n,lefttop,rightbottom);
		b.balloons = ballons;
		
		double recv = (rightbottom.getX()-lefttop.getX())*(rightbottom.getY()-lefttop.getY())*(rightbottom.getZ()-lefttop.getZ());
		System.out.println(Math.round(recv - b.getMaxBallV()));
	}
}

class Balloon {
	private int x;
	private int y;
	private int z;
	private double r;
	/**
	 * @param x
	 * @param y
	 * @param z
	 */
	public Balloon(int x, int y, int z, double r) {
		super();
		this.x = x;
		this.y = y;
		this.z = z;
		this.r = r;
	}
	/**
	 * @return the r
	 */
	public double getR() {
		return r;
	}
	/**
	 * @param r the r to set
	 */
	public void setR(double r) {
		this.r = r;
	}
	/**
	 * @return the x
	 */
	public int getX() {
		return x;
	}
	/**
	 * @param x the x to set
	 */
	public void setX(int x) {
		this.x = x;
	}
	/**
	 * @return the y
	 */
	public int getY() {
		return y;
	}
	/**
	 * @param y the y to set
	 */
	public void setY(int y) {
		this.y = y;
	}
	/**
	 * @return the z
	 */
	public int getZ() {
		return z;
	}
	/**
	 * @param z the z to set
	 */
	public void setZ(int z) {
		this.z = z;
	}
	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		return "Point [x=" + x + ", y=" + y + ", z=" + z + "]";
	}
	
}
分享到:
评论

相关推荐

    vc++ opengl 炫彩盒子打开气球上升

    在本项目中,"vc++ opengl 炫彩盒子打开气球上升"是一个使用Microsoft Visual C++(简称vc++)编程环境,并结合OpenGL图形库和C++语言实现的交互式三维动画。OpenGL是一个跨语言、跨平台的编程接口,主要用于渲染2D...

    OpenGL从盒子飞出的气球

    鼠标放在屏幕最上边,点击第一个图标,盒子打开气球从盒子飞出来,气球颜色和位置是rand的,每次打开都不同

    OpenGl实现的彩色盒子

    用OpenGl实现的一个彩色的盒子缓缓的打开,里面缓缓飘出若干气球。。

    FLASH游戏物理盒子代码

    "FLASH游戏物理盒子代码"指的是使用Flash编程语言ActionScript实现的一种物理引擎,用于模拟游戏中的物理效果,如重力、碰撞检测、动量守恒等。这个压缩包文件"physical_box"可能包含了实现这种物理引擎的源代码、...

    小学数学逻辑推理题精选100题.doc

    逻辑分析:根据蓝盒子比黄盒子大,蓝盒子比黑盒子小,黑盒子比红盒子小,可以推断出黑盒子大于红盒子,小于蓝盒子。因此,黑盒子是第二大的,红盒子是最小的。 答案:黑盒子、蓝盒子、黄盒子、红盒子。 9. 黄、李...

    c++实现算法分析各种经典题型

    - 文件中的第二个例子使用枚举法解决盒子里的气球问题,即考虑所有可能的情况来找到最大半径的气球。 - `vis`数组用于标记已经处理过的气球,避免重复计算。 5. **结构体与数据存储**: - 定义了`struct po`来...

    (临考储备)2013中考英语复习精品资料 超值阅读练习35 人教新目标版

    2. 那个金属盒子是用来改变重量的。气球上携带的绳索末端系着这个金属盒,它可以装水或者为空,这样就能调整气球的重量。因此,选项A(改变重量)是正确的用途。 3. 当气球飞得更高时,气球内的温度开始下降。气球...

    大学联谊活动策划书.doc

    【大学联谊活动策划书】 活动名称:友情的呼唤,沟通的开头—高校班级联谊活动 活动目的:这次大学联谊活动的主要...4. 准备游戏所需道具:如气球、眼罩、绳子、笔、小纸条、剪刀、盒子、报纸等,确保活动顺利进行。

    四年级数学上册 第六单元《可能性》单元综合检测卷 苏教版 试题.doc

    A选项表示一定是红气球,说明盒子只放了红气球;B选项可能是红气球,表示红气球和黄气球都有可能;C选项既有可能是红气球也有可能是黄气球;D选项表示可能是黄气球,意味着至少有两种颜色。 5. 至少摸出5个球才能...

    中考英语复习精品资料 阅读练习29.doc

    这个金属盒子可以装水或保持空状态,因此可以用来调整热气球的重量。此外,他们还带了一些沙袋,以便在需要时改变热气球的浮力。随着太阳升起,热气球逐渐升高,达到了3000米的高度,此时空气变得非常寒冷,热气球内...

    小学一年级数学练习题(趣味题).doc

    由条件可知,蓝盒子 &gt; 黄盒子,蓝盒子 黑盒子,黑盒子 红盒子,所以从大到小的顺序是:红盒子,蓝盒子,黄盒子,黑盒子。 9. 通过排除法,可以得出甲姓李,乙姓黄,丙姓张。 10. 本题是逻辑推理。小春得到的不是蓝...

    大学联谊活动方案范文精选多篇2021.pdf

    - **吹盒子**:两人蒙眼互相吹盒子,盒子过界者胜利。 - **写开心与不开心的事**:匿名分享,增加趣味性。 - **晚会结束后的KTV唱歌**作为庆祝活动。 7. **活动前期准备**:包括班会讨论、与其他班级班委协商、...

    大学联谊方案5篇.docx

    - **吹盒子**:蒙眼互相吹动盒子,将盒子吹至对方一侧获胜。 5. **心情分享**:晚会尾声,参与者写下当天最开心和最不开心的事,由主持人宣读,增加趣味性。 6. **结束**:主持人宣布晚会结束,大家共同清理现场,...

    可爱卡通小镇场景 :Cartoon Town - Low Poly Assets 1.4.2

    道具:气球架、气球 x16、垃圾桶 x3、礼物、热气球 x3、贝壳 x4、雨伞 x5、银行、船、盒子、浮标 x2、时钟、云朵、彩旗、花箱、棕榈树、树木、泡泡门、固定墙 x2、柱子、道路终点标志、树标志、骷髅、、帐篷、交通...

    动量定理与动量守恒定律典型例题解析.doc

    例1中,一个物体在盒子内滑行,最终与盒子右壁碰撞。动量定理在这里用于计算物体滑行的时间,而动量守恒定律则用于分析碰撞前后系统的总动量。由于系统在水平方向没有外力作用,碰撞前后系统的总动量应保持不变。 ...

    算法设计与分析习题课PPT学习教案.pptx

    7. 盒子里的气球问题: 这是一个物理模型的抽象,涉及到图论中的邻接关系和拓扑排序。解决这类问题需要理解气球之间的相互作用和它们在三维空间中的位置,可能需要使用图算法来确定扩展气球的最佳顺序。 以上就是...

    教案工艺小作品制作.pdf

    3. 自制热气球:利用纸片制作成气球形状,通过电吹风产生的热气,热气球会上升。这是一个有趣的科学实验,演示了热空气上升的原理。 4. 自制手电筒:将废旧易拉罐改造为手电筒,利用电池和灯泡,只需简单连接电线和...

    大班科学活动教案:有趣的弹性.docx

    1. 以小丑娃娃的出现为引子,引发幼儿的兴趣,通过小丑娃娃从盒子里蹦出的情境,引导幼儿思考小丑如何实现这一动作,从而引入弹簧和弹性概念。 2. 展示弹簧,让孩子们亲手操作,观察弹簧在受力时的形变和释放后恢复...

    三年级应用题(2)(1).doc

    总共有280个红气球和140个黄气球,6个班平分这些气球,需要将气球总数(420)除以班级数(6),得到每班平均购买的气球数为70个。 3. 这是一道关于倍数的问题。五年级种了48棵树,六年级种的是五年级的2倍,所以六...

Global site tag (gtag.js) - Google Analytics