首页 > 代码库 > UVA How Big Is It?
UVA How Big Is It?
题目如下:
How Big Is It?
Ian‘s going to California, and he has to pack his things, including hiscollection of circles. Given a set of circles, your program mustfind the smallest rectangular box in which they fit.All circles must touch the bottom of the box. The figure below showsan acceptable packing for a set of circles (although this may not bethe optimal packing for these particular circles). Note that in anideal packing, each circle should touch at least one other circle(but you probably figured that out).How Big Is It? |
Input
The first line of input contains a single positive decimal integer n,n<=50. This indicates the number of lines which follow. Thesubsequentn lines each contain a series of numbers separated byspaces. The first number on each of these lines is a positive integerm,m<=8, which indicates how many other numbers appear on thatline. The nextm numbers on the line are the radii of the circleswhich must be packed in a single box. These numbers need not beintegers.Output
For each data line of input, excluding the first line of input containingn, your program must output the size of the smallest rectangle which canpack the circles. Each case should be output on a separate line by itself,with three places after the decimal point. Do not output leading zeroesunless the number is less than 1, e.g.0.543
.Sample Input
3 3 2.0 1.0 2.0 4 2.0 2.0 2.0 2.0 3 2.0 1.0 4.0
Sample Output
9.657 16.000 12.657
求能放置所给圆的矩形的最小长度。这道题有一些细节没注意到的话就会无限WA,刚开始我想的是把所有圆全排列,把每个情况的长度算出来求最小值,结果WA了,因为算每个情况长度的时候,我是假设每个圆都与前一个圆相切,实际并不一定这样,比如有两个很大的圆相切,他们中间可以有许多小圆,与这两个圆并不一定相切,所以用之前的方法算出来结果就小了。在网上参考了别人的代码,发现他们是设置了一个数组记录圆心坐标,求每个圆心坐标的时候,是求出与之前圆相切的圆的圆心坐标的最大值,因为目前考虑的圆肯定是最右的圆,所以它的圆心坐标肯定最大,又由于要矩形长度最短,所以至少与之前的某一个圆相切(不一定是前一个)。最左边的坐标就是圆心坐标减去半径大小的最小值,最右边的坐标就是圆心坐标加上半径大小的最大值,最右边减去最左边的值的最小值就是矩形的最小长度。
AC的代码如下:
<script src="https://code.csdn.net/snippets/427330.js" type="text/javascript"></script>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。