Dada uma lista de círculos, produza a área do menor retângulo contendo

28

Você receberá uma lista de raios. Você deve imprimir a área do menor retângulo no qual todos eles se encaixam.

Por exemplo, dada a lista que [5,3,1.5]você produziria 157.460.

Esta é a imagem:

A largura é 15.7460 e a altura é 10, então a área é 157.460

Regras:

  • Você obtém a lista via stdin ou argumento de função, gera a resposta via stdout ou retorno de função.

  • Os raios terão no máximo 2 casas decimais.

  • A lista terá um comprimento entre 2 e 6.

  • A saída deve ser precisa com 3 casas decimais ou mais.

  • Se você precisar, π = 3,1416.

Casos de teste:

  • [5,3,1.5] = 157.460

  • [9,4,8,2] = 733.431- trabalhando aqui .

  • [18,3,1] = 1296.000

O menor código em bytes vence.

code-golf math optimization Tim
fonte
Related
DJMcMayhem
1
não vejo um critério de vitória objetivo
Maltysen 30/08/16
essa é uma das nossas regras mais centrais
Maltysen
2
@ Tim A maioria é de código de golfe, com o objetivo de codificá-lo no menor número de bytes. Eu acho que isso seria um bom desafio para o código de golfe, pois tem uma especificação exata.
Xnor
Eu recomendo se livrar da condição "arredondado não truncado" porque é periférico à tarefa, e alguns idiomas podem fazer isso enquanto outros precisam de codificação extra para que isso aconteça. Não tenho certeza se você pretende que seja correto gerar mais de três casas decimais, mas sugiro permitir isso também.
Xnor

Respostas:

16

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

Como funciona

Escrevemos o problema da seguinte maneira: minimize c sobre as variáveis a , b , c , x 1 , y 1 ,…, x n , y n , em que

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

Obviamente, estamos usando uma biblioteca de otimização externa sobre essas restrições, mas você não pode simplesmente alimentá-las com qualquer otimizador antigo - até mesmo com o Mathematica NMinimize fica preso nos mínimos locais para esses minúsculos casos de teste. Se você observar atentamente as restrições, verá que elas constituem um programa quadrático com restrição quadrática e encontrar o ideal global para um QCQP não convexo é difícil para o NP. Então, precisamos de uma magia incrivelmente poderosa. Escolhi o solucionador de força industrial SCIP , que é o único solucionador global de QCQP que eu poderia encontrar com uma licença gratuita para uso acadêmico. Felizmente, ele tem algumas ligações Python muito legais.

Entrada e saída

Passe a lista de raios em stdin, como [5,3,1.5]. O resultado mostra objective value:a área de rectângulo, x1, x2dimensões do retângulo,x3 área rectângulo de novo, x4, x5primeiras coordenadas do centro do círculo, x6, x7segundo as coordenadas do centro do círculo, etc.

Casos de teste

[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

Isso é melhor que a solução do OP. As dimensões exatas são 18 por 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)

Casos de bônus

[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
fonte
Que pena que o último dê um pequeno erro de arredondamento, mas bom trabalho!
Tim
Parece-me que [1,2,3,4,5] poderia ser melhorado fazendo os círculos 3 e 5 serem tocados também, girando o raio 4 / raio 5 na diagonal no sentido horário ligeiramente (o raio 1 do círculo teria que O meu instinto e meus cálculos indicam que um retângulo longo e fino pode conter o raio 4 / raio 5 círculos com mais eficiência do que um quadrado.
Level River St
@LevelRiverSt Não concordo. Mover 3 para cima para tocar 5 empurra 4 para a direita (no sentido anti-horário de 5), não o deixa mover para a esquerda (no sentido horário de 5). A configuração do meu programa é (7 + 4√3) × (9 + √ (29 + 16√3)) ≈ 13,9282 × 16,5308 ≈ 230,244, enquanto a configuração sugerida é (30 + 15√3) / 4 × (36 + 3 √5 + 6√15) / 4 ≈ 13,9952 × 16,4865 ≈ 230,732.
Anders Kaseorg