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 + "]";
}
}
分享到:
相关推荐
鼠标放在屏幕最上边,点击第一个图标,盒子打开气球从盒子飞出来,气球颜色和位置是rand的,每次打开都不同
用的是vc软件,在MFC框架下用opengl和c++编写的,实现了炫彩盒子打开的同时气球上升的画面,场景不错,感觉对初学者有帮助
一个unity气球模型;一个unity气球模型;一个unity气球模型;一个unity气球模型;一个unity气球模型;一个unity气球模型
六一儿童节,小朋友们做踩气球游戏,气球的编号是1~100,两位小朋友各踩了一些气球,要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负,判断的规则是这样的:如果两人都说了真话,数字...
通过切换背景图位置显示不同气球 气球宽高 118* 168 位置间距X:140 Y: 176 坐标的确定:横坐标0 1 2 3 纵坐标 0 1 2(4*3的精灵图),横坐标通过 下标%4 得出 纵坐标通过 parseInt(下标/4)得出 初始化设置 :初始...
VBA 版打气球游戏 Excel VBA 版打气球游戏 Excel VBA 版打气球游戏 Excel VBA 版打气球游戏 Excel VBA 版打气球游戏 Excel VBA 版打气球游戏 Excel VBA 版打气球游戏 Excel VBA 版打气球游戏 Excel
压缩包里有两种打气球玩法,点开网页即可打气球。打中气球会加分,当气球触碰到网页顶部则游戏结束。
中班数学气球PPT课件.pptx
用OpenGl实现的一个彩色的盒子缓缓的打开,里面缓缓飘出若干气球。。
打气球 这个小游戏挺有意思的,传出来给大家分享一下!!
利用单片机的蜂鸣器实现告白气球的旋律,下载后可直接播放,单片机型号不同也可通过修改引脚来实现音乐的播放
maya气球爆炸
java 飞舞的气球 java 飞舞的气球 java 飞舞的气球
将气球塔防5安装后找到安装的文件夹将此文件拖入即可注册码随便填
文件包含打气球的实现代码、功能代码思路讲解、视频演示和讲解。打气球的小游戏:在开始界面根据气球出现的数量和移动速度分为三个游戏等级可供选择,点击某个等级后转到对应难度的游戏。
里面包括需求分析等,注释多于代码,大家可以更好地理解,互相学习,浏览器打开即可运行,相当于一个小游戏
2021商场七夕情人节气球雨相亲派对“告白气球”活动策划方案.pptx
封装可以扩散的气球 封装气球对象.html
易语言气球提示框表情源码,气球提示框表情
制作网页气球提示网页提示气球温馨提示友好窗口