Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Mathematics and Computer Science
How Big Is It?
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 12, Accepted users: 10
Problem 10044 : No special judgement
Problem description
  Ianí»s going to California, and he has to pack his things, including his collection of circles. Given a set of circles, your program must find the smallest rectangular box in which they fit. All circles must touch the bottom of the box. The figure below shows an acceptable packing for a set of circles (although this may not be the optimal packing for these particular circles). Note that in an ideal packing, each circle should touch at least one other circle (but you probably figured that out).


Input
  The first line of input contains a single positive decimal integer n, n < 50. This indicates the number of lines which follow. The subsequent n lines each contain a series of numbers separated by spaces. The first number on each of these lines is a positive integer m, m < 8, which indicates how many other numbers appear on that line. The next m numbers on the line are the radii of the circles which must be packed in a single box. These numbers need not be integers.

Output
  For each data line of input, excluding the first line of input containing n, your program must output the size of the smallest rectangle which can pack the circles. Each case should be output on a separate line by itself, with three places after the decimal point. Do not output leading zeroes unless 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
Problem Source
  2006 MSU Local Programming Contest

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:327 today,10600161 total, since 2010-05-07