Вам будет предоставлен список радиусов, вы должны вывести область наименьшего прямоугольника, в которую они все поместятся.

Например, учитывая список, который [5,3,1.5]вы бы вывели 157.460.

Это изображение:

Ширина 15.7460, а высота 10, поэтому площадь 157.460.

Правила:

Вы получаете список через стандартный ввод или аргумент функции, выводите ответ через стандартный вывод или функцию возврата.
Радиусы будут иметь не более 2 знаков после запятой.
Список будет иметь длину от 2 до 6.
Вывод должен быть точным с точностью до 3 знаков после запятой.
Если вам нужно, я = 3.1416.

Тестовые случаи:

[5,3,1.5] = 157.460
[9,4,8,2] = 733.431- работаю здесь .
[18,3,1] = 1296.000

Самый короткий код в байтах побеждает.

code-golf math optimization Тим
источник

Связанные

DJMcMayhem

я не вижу объективного критерия победы

Maltysen

это одно из наших самых

важных

@Tim Большинство из них представляют собой кодовый гольф с целью его кодирования в наименьшем количестве байтов. Я думаю, что это было бы хорошим испытанием для игры в гольф, поскольку у него есть точная спецификация.

xnor

Я рекомендую избавиться от условия «округлено, не усечено», потому что оно является второстепенным для задачи, и некоторые языки могут это делать, в то время как другим требуется дополнительное кодирование, чтобы это произошло. Я не уверен, что вы хотите, чтобы все было в порядке, чтобы вывести более 3 десятичных знаков, но я бы посоветовал разрешить это тоже.

xnor

Python 2 + PySCIPOpt , 267 байт

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

Как это работает

Запишем задачу следующим образом: минимизировать c над переменными a , b , c , x ₁ , y ₁ ,…, x _n , y_n , где

аб ≤ c ;
r _i ≤ x _i ≤ a - r _i и r _i ≤ y _i ≤ b - y _i , для 1 ≤ i ≤ n ;
( x _i - x _j ) ² + ( y _i - y_j )² ≥ ( r _i + r _j )² , для 1 ≤ j < i ≤ n .

Очевидно, что мы используем внешнюю библиотеку оптимизации для этих ограничений, но вы не можете просто передать их любому старому оптимизатору - даже Mathematica NMinimizeзастревает в локальных минимумах для этих крошечных тестовых случаев. Если вы внимательно посмотрите на ограничения, вы увидите, что они представляют собой квадратично ограниченную квадратичную программу , и найти глобальный оптимум для невыпуклого QCQP сложно с точки зрения NP. Поэтому нам нужна невероятно мощная магия. Я выбрал промышленный анализатор SCIP , который является единственным глобальным решателем QCQP, который я смог найти с такой бесплатной лицензией для академического использования. К счастью, у него есть очень хорошие привязки Python.

Вход и выход

Передайте список радиусов в stdin, как [5,3,1.5]. Вывод показывает objective value:прямоугольник область, x1, x2прямоугольник, размеры x3прямоугольника площадь снова, x4, x5первый круг Координаты центра,x6 , x7вторые координаты центра окружности и т.д.

Контрольные примеры

`[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`

Это лучше, чем решение ОП. Точные размеры 18 на 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)

Бонусные случаи

`[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)

Андерс Касеорг
источник

Позор последний дает небольшую ошибку округления, но хорошая работа!

Тим

Мне кажется, что [1, 2, 3, 4, 5] можно улучшить, сделав также прикосновение к радиусу 3 и радиусу 5, а затем слегка повернув его по часовой стрелке на 4 радиуса (радиус 1). быть убранным с дороги, но для этого есть много мертвого пространства. И мой инстинкт, и мои расчеты показывают, что длинный тонкий прямоугольник может содержать радиус 4 / радиус 5 окружностей более эффективно, чем квадратный.

Level River St

@LevelRiverSt Я не согласен. Перемещение 3 вверх к касанию 5 отодвинуло 4 вправо (против 5 против часовой стрелки), не позволяя ему двигаться влево (по часовой стрелке от 5) Конфигурация моей программы (7 + 4√3) × (9 + √ (29 + 16√3)) ≈ 13,9282 × 16,5308 ≈ 230,244, в то время как ваша рекомендуемая конфигурация составляет (30 + 15√3) / 4 × (36 + 3) √5 + 6√15) / 4 ≈ 13.9952 × 16.4865 ≈ 230.732.

Андерс Касеорг

Учитывая список окружностей, выведите область наименьшего содержащего прямоугольника

Ответы:

Python 2 + PySCIPOpt , 267 байт

Как это работает

Вход и выход

Контрольные примеры

`[5,3,1.5]` ↦ `157.459666673757`

`[9,4,8,2]` ↦ `709.061485909243`

`[18,3,1]` ↦ `1295.999999999`

Бонусные случаи

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

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

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

Учитывая список окружностей, выведите область наименьшего содержащего прямоугольника

Ответы:

Python 2 + PySCIPOpt , 267 байт

Как это работает

Вход и выход

Контрольные примеры

[5,3,1.5] ↦ 157.459666673757

[9,4,8,2] ↦ 709.061485909243

[18,3,1] ↦ 1295.999999999

Бонусные случаи

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

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

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

`[5,3,1.5]` ↦ `157.459666673757`

`[9,4,8,2]` ↦ `709.061485909243`

`[18,3,1]` ↦ `1295.999999999`

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

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

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