Étant donné une liste de cercles, affichez la zone du plus petit rectangle contenant

28

Vous recevrez une liste de rayons, vous devez sortir la zone du plus petit rectangle dans lequel ils s'inscriront tous.

Par exemple, étant donné la liste que [5,3,1.5]vous produirez 157.460.

Voici l'image:

La largeur est de 15,7460 et la hauteur de 10, donc la zone est de 157,460

Règles:

  • Vous obtenez la liste via stdin ou l'argument de fonction, affichez la réponse via stdout ou retour de fonction.

  • Les rayons auront au plus 2 décimales.

  • La liste aura une longueur comprise entre 2 et 6.

  • La sortie doit être précise à 3 décimales ou plus.

  • Si vous en avez besoin, π = 3,1416.

Cas de test:

  • [5,3,1.5] = 157.460

  • [9,4,8,2] = 733.431- travailler ici .

  • [18,3,1] = 1296.000

Le code le plus court en octets gagne.

code-golf math optimization Tim
la source
Connexes
DJMcMayhem
1
je ne vois pas de critère de victoire objectif
Maltysen
c'est l'une de nos règles les plus centrales
Maltysen
2
@Tim La plupart sont du golf de code, dans le but de le coder dans le moins d'octets. Je pense que cela ferait un bon défi de golf de code, car il a une spécification exacte.
xnor
Je recommande de se débarrasser de la condition «arrondi non tronqué» car elle est périphérique à la tâche, et certaines langues peuvent simplement le faire tandis que d'autres ont besoin d'un codage supplémentaire pour y arriver. Je ne suis pas sûr que vous souhaitiez qu'il soit correct de sortir plus de 3 décimales, mais je suggérerais d'autoriser cela également.
xnor

Réponses:

16

Python 2 + PySCIPOpt , 267 octets

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()

Comment ça marche

Nous écrivons le problème comme suit: minimiser c sur les variables a , b , c , x 1 , y 1 ,…, x n , y n , où

  • ab ≤ c ;
  • r i ≤ x i ≤ a - r i et r i ≤ y i ≤ b - y i , pour 1 ≤ i ≤ n ;
  • ( x i - x j ) 2 + ( y i - y j ) 2 ≥ ( r i + r j ) 2 , pour 1 ≤ j < i ≤ n .

Évidemment, nous utilisons une bibliothèque d'optimisation externe sur ces contraintes, mais vous ne pouvez pas simplement les alimenter à n'importe quel ancien optimiseur - même Mathematica NMinimizeest bloqué aux minima locaux pour ces minuscules cas de test. Si vous regardez attentivement les contraintes, vous verrez qu'elles constituent un programme quadratique à contraintes quadratiques , et trouver l'optimum global pour un QCQP non convexe est NP-difficile. Nous avons donc besoin d'une magie incroyablement puissante. J'ai choisi le solveur de puissance industrielle SCIP , qui est le seul solveur QCQP mondial que j'ai pu trouver avec autant de licence gratuite pour un usage académique. Heureusement, il a de très belles liaisons Python.

Entrée et sortie

Passez la liste des rayons sur stdin, comme [5,3,1.5]. La montre de sortie objective value:zone rectangle, x1, x2dimensions rectangle, x3zone rectangulaire à nouveau, x4, x5des premières coordonnées du centre du cercle, x6, x7deuxièmes coordonnées du centre du cercle, etc.

Cas de test

[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

C'est mieux que la solution de l'OP. Les dimensions exactes sont 18 par 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)

Cas bonus

[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)
Anders Kaseorg
la source
Dommage que le dernier donne une légère erreur d'arrondi, mais beau travail!
Tim
Il me semble que [1,2,3,4,5] pourrait être amélioré en touchant également les cercles de rayon 3 et de rayon 5, puis en tournant légèrement le rayon 4 / rayon 5 en diagonale dans le sens horaire (le cercle de rayon 1 devrait "
Level River St
@LevelRiverSt Je ne suis pas d'accord. Déplacer 3 vers le haut pour toucher 5 repousserait 4 vers la droite (dans le sens antihoraire de 5), sans le laisser se déplacer vers la gauche (dans le sens horaire de 5). La configuration de mon programme est (7 + 4√3) × (9 + √ (29 + 16√3)) ≈ 13.9282 × 16.5308 ≈ 230.244, tandis que votre configuration suggérée est (30 + 15√3) / 4 × (36 + 3 √5 + 6√15) / 4 ≈ 13,9952 × 16,4865 ≈ 230,732.
Anders Kaseorg