Given a list of circles, output the area of the smallest containing rectangle You will be given a list of radii, you must output the area of the smallest rectangle which they will all fit in.

For example, given the list [5,3,1.5] you would output 157.460.

This is the image:



The width is 15.7460 and the height is 10, so the area is 157.460

Rules:


You get the list via stdin or function argument, output the answer via stdout or function return.
The radii will have at most 2 decimal places.
The list will have a length between 2 and 6.
The output should be accurate to 3 decimal places or more.
If you need, π = 3.1416.


Test cases:


[5,3,1.5] = 157.460
[9,4,8,2] = 733.431 - working here.
[18,3,1] = 1296.000




Shortest code in bytes wins.
Python 2 + PySCIPOpt, 267 bytes



from pyscipopt import*
R=input()
m=Model()
V,C=m.addVar,m.addCons
a,b,c=V(),V(),V()
m.setObjective(c)
C(a*b&lt;=c)
P=[]
for r in R:
 x,y=V(),V();C(r&lt;=x);C(x&lt;=a-r);C(r&lt;=y);C(y&lt;=b-r)
 for u,v,s in P:C((x-u)**2+(y-v)**2&gt;=(r+s)**2)
 P+=(x,y,r),
m.optimize()
m.printBestSol()


How it works

We write the problem as follows: minimize c over variables a, b, c, x1, y1, …, xn, yn, where


ab ≤ c;
ri ≤ xi ≤ a − ri and ri ≤ yi ≤ b − yi, for 1 ≤ i ≤ n;
(xi − xj)2 + (yi − yj)2 ≥ (ri + rj)2, for 1 ≤ j &lt; i ≤ n.


Obviously, we’re using an external optimization library on these constraints, but you can’t just feed them to any old optimizer—even Mathematica’s NMinimize gets stuck at local minima for these tiny test cases.  If you stare closely at the constraints, you’ll see that they constitute a quadratically-constrained quadratic program, and finding the global optimum for a non-convex QCQP is NP-hard.  So we need some incredibly high-powered magic.  I chose the industrial-strength solver SCIP, which is the only global QCQP solver I could find with so much as a free license for academic use.  Happily, it has some very nice Python bindings.

Input and output

Pass the radius list on stdin, like [5,3,1.5].  The output shows objective value: rectangle area, x1, x2 rectangle dimensions, x3 rectangle area again, x4, x5 first circle center coordinates, x6, x7 second circle center coordinates, etc.

Test cases

[5,3,1.5] ↦ 157.459666673757



SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.04
Solving Nodes      : 187
Primal Bound       : +1.57459666673757e+02 (9 solutions)
Dual Bound         : +1.57459666673757e+02
Gap                : 0.00 %
objective value:                     157.459666673757
x1                                                 10   (obj:0)
x2                                   15.7459666673757   (obj:0)
x3                                   157.459666673757   (obj:1)
x4                                                  5   (obj:0)
x5                                                  5   (obj:0)
x6                                                  7   (obj:0)
x7                                   12.7459666673757   (obj:0)
x8                                                1.5   (obj:0)
x9                                   10.4972522849871   (obj:0)


[9,4,8,2] ↦ 709.061485909243

This is better than the OP’s solution.  The exact dimensions are 18 by 29 + 6√3.



SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 1.07
Solving Nodes      : 4650
Primal Bound       : +7.09061485909243e+02 (6 solutions)
Dual Bound         : +7.09061485909243e+02
Gap                : 0.00 %
objective value:                     709.061485909243
x1                                                 18   (obj:0)
x2                                   39.3923047727357   (obj:0)
x3                                   709.061485909243   (obj:1)
x4                                                  9   (obj:0)
x5                                   30.3923047727357   (obj:0)
x6                                                 14   (obj:0)
x7                                   18.3923048064677   (obj:0)
x8                                                  8   (obj:0)
x9                                                  8   (obj:0)
x10                                                 2   (obj:0)
x11                                  19.6154311552252   (obj:0)


[18,3,1] ↦ 1295.999999999



SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 13
Primal Bound       : +1.29599999999900e+03 (4 solutions)
Dual Bound         : +1.29599999999900e+03
Gap                : 0.00 %
objective value:                       1295.999999999
x1                                   35.9999999999722   (obj:0)
x2                                                 36   (obj:0)
x3                                     1295.999999999   (obj:1)
x4                                   17.9999999999722   (obj:0)
x5                                                 18   (obj:0)
x6                                   32.8552571627738   (obj:0)
x7                                                  3   (obj:0)
x8                                                  1   (obj:0)
x9                                                  1   (obj:0)


Bonus cases

[1,2,3,4,5] ↦ 230.244214912998



SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 401.31
Solving Nodes      : 1400341
Primal Bound       : +2.30244214912998e+02 (16 solutions)
Dual Bound         : +2.30244214912998e+02
Gap                : 0.00 %
objective value:                     230.244214912998
x1                                   13.9282031800476   (obj:0)
x2                                    16.530790960676   (obj:0)
x3                                   230.244214912998   (obj:1)
x4                                                  1   (obj:0)
x5                                   9.60188492354373   (obj:0)
x6                                    11.757778088743   (obj:0)
x7                                   3.17450418828415   (obj:0)
x8                                                  3   (obj:0)
x9                                    13.530790960676   (obj:0)
x10                                  9.92820318004764   (obj:0)
x11                                   12.530790960676   (obj:0)
x12                                                 5   (obj:0)
x13                                                 5   (obj:0)


[3,4,5,6,7] ↦ 553.918025310597



SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 90.28
Solving Nodes      : 248281
Primal Bound       : +5.53918025310597e+02 (18 solutions)
Dual Bound         : +5.53918025310597e+02
Gap                : 0.00 %
objective value:                     553.918025310597
x1                                   21.9544511351279   (obj:0)
x2                                   25.2303290086403   (obj:0)
x3                                   553.918025310597   (obj:1)
x4                                                  3   (obj:0)
x5                                   14.4852813557912   (obj:0)
x6                                   4.87198593295855   (obj:0)
x7                                   21.2303290086403   (obj:0)
x8                                   16.9544511351279   (obj:0)
x9                                                  5   (obj:0)
x10                                                 6   (obj:0)
x11                                                 6   (obj:0)
x12                                  14.9544511351279   (obj:0)
x13                                  16.8321595389753   (obj:0)


[3,4,5,6,7,8] ↦ 777.87455544487



SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 218.29
Solving Nodes      : 551316
Primal Bound       : +7.77874555444870e+02 (29 solutions)
Dual Bound         : +7.77874555444870e+02
Gap                : 0.00 %
objective value:                      777.87455544487
x1                                   29.9626413867546   (obj:0)
x2                                   25.9614813640722   (obj:0)
x3                                    777.87455544487   (obj:1)
x4                                   13.7325948669477   (obj:0)
x5                                   15.3563780595534   (obj:0)
x6                                   16.0504838821134   (obj:0)
x7                                   21.9614813640722   (obj:0)
x8                                   24.9626413867546   (obj:0)
x9                                   20.7071098175984   (obj:0)
x10                                                 6   (obj:0)
x11                                  19.9614813640722   (obj:0)
x12                                                 7   (obj:0)
x13                                                 7   (obj:0)
x14                                  21.9626413867546   (obj:0)
x15                                  8.05799919177801   (obj:0)