29
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ Related \$\endgroup\$
    – DJMcMayhem
    Commented Aug 30, 2016 at 1:44
  • 1
    \$\begingroup\$ i don't see an objective winning criterion \$\endgroup\$
    – Maltysen
    Commented Aug 30, 2016 at 1:50
  • \$\begingroup\$ that's one of our most central rules \$\endgroup\$
    – Maltysen
    Commented Aug 30, 2016 at 1:52
  • 2
    \$\begingroup\$ @Tim Most are code golf, with the goal of coding it in the fewest bytes. I think this would make a good code golf challenge, as it has an exact spec. \$\endgroup\$
    – xnor
    Commented Aug 30, 2016 at 1:56
  • \$\begingroup\$ I recommend getting rid of the "rounded not truncated" condition because it's peripheral to the task, and some languages can just do it while others need extra coding to make it happen. I'm not sure if you intend it to be OK to output more than 3 decimal places, but I'd suggest allowing that too. \$\endgroup\$
    – xnor
    Commented Aug 30, 2016 at 1:58

1 Answer 1

Reset to default
17
+50
\$\begingroup\$

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<=c)
P=[]
for r in R:
 x,y=V(),V();C(r<=x);C(x<=a-r);C(r<=y);C(y<=b-r)
 for u,v,s in P:C((x-u)**2+(y-v)**2>=(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 < 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

5,3,1.5

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.

9,4,8,2

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

18,3,1

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

1,2,3,4,5

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

3,4,5,6,7

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

3,4,5,6,7,8

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)
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Shame the last one gives a slight rounding error, but nice work! \$\endgroup\$
    – Tim
    Commented Jul 27, 2017 at 9:55
  • \$\begingroup\$ It looks to me like [1,2,3,4,5] could be improved by making the radius 3 and radius 5 circles touch also, then rotating the radius 4 / radius 5 diagonal clockwise slightly (the radius 1 circle would have to be moved out of the way but there is plenty of dead space for that. Both my instinct and my calculations indicate that a long, thin rectangle can contain the radius 4/ radius 5 circles more efficiently than a squarer one. \$\endgroup\$
    – Level River St
    Commented Jul 30, 2017 at 1:16
  • 1
    \$\begingroup\$ @LevelRiverSt I don’t agree. Moving 3 up to touch 5 would push 4 away to the right (counterclockwise from 5), not let it move left (clockwise from 5). My program’s configuration is (7 + 4√3) × (9 + √(29 + 16√3)) ≈ 13.9282 × 16.5308 ≈ 230.244, while your suggested configuration is (30 + 15√3)/4 × (36 + 3√5 + 6√15)/4 ≈ 13.9952 × 16.4865 ≈ 230.732. \$\endgroup\$
    – Anders Kaseorg
    Commented Jul 30, 2017 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.