Diberikan daftar lingkaran, output area persegi panjang terkecil yang mengandung

28

Anda akan diberikan daftar jari-jari, Anda harus menampilkan area persegi panjang terkecil yang semuanya cocok.

Misalnya, mengingat daftar [5,3,1.5]yang akan Anda keluarkan 157.460.

Ini gambarnya:

Lebarnya 15,7460 dan tingginya 10, jadi luasnya 157,460

Aturan:

  • Anda mendapatkan daftar melalui stdin atau argumen fungsi, mengeluarkan jawaban melalui stdout atau fungsi kembali.

  • Jari-jari akan memiliki paling banyak 2 tempat desimal.

  • Daftar ini akan memiliki panjang antara 2 dan 6.

  • Outputnya harus akurat hingga 3 tempat desimal atau lebih.

  • Jika Anda perlu, π = 3.1416.

Kasus uji:

  • [5,3,1.5] = 157.460

  • [9,4,8,2] = 733.431- bekerja di sini .

  • [18,3,1] = 1296.000

Kode terpendek dalam byte menang.

code-golf math optimization Tim
sumber
Terkait
DJMcMayhem
1
saya tidak melihat kriteria kemenangan yang objektif
Maltysen
itulah salah satu aturan paling sentral kami
Maltysen
2
@Tim Sebagian besar adalah kode golf, dengan tujuan mengkodekannya dalam byte paling sedikit. Saya pikir ini akan menjadi tantangan golf kode yang bagus, karena memiliki spesifikasi yang tepat.
xnor
Saya merekomendasikan untuk menyingkirkan kondisi "rounded not terpotong" karena itu periferal untuk tugas, dan beberapa bahasa hanya dapat melakukannya sementara yang lain membutuhkan pengkodean tambahan untuk mewujudkannya. Saya tidak yakin apakah Anda bermaksud OK untuk menghasilkan lebih dari 3 tempat desimal, tapi saya sarankan untuk mengizinkannya juga.
xnor

Jawaban:

16

Python 2 + PySCIPOpt , 267 byte

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

Bagaimana itu bekerja

Kami menulis masalah sebagai berikut: meminimalkan c lebih dari variabel a , b , c , x 1 , y 1 , ..., x n , y n , di mana

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

Jelas, kami menggunakan pustaka pengoptimalan eksternal pada kendala ini, tetapi Anda tidak bisa hanya memberi mereka ke pengoptimal lama — bahkan Mathematica NMinimizeakan terjebak di minimum lokal untuk kasus kecil ini. Jika Anda mengamati dengan seksama kendala, Anda akan melihat bahwa mereka merupakan program kuadratik yang dibatasi secara kuadratik , dan menemukan bahwa optimum global untuk QCQP non-cembung adalah NP-hard. Jadi kita membutuhkan sihir bertenaga luar biasa. Saya memilih pemecah kekuatan industri SCIP , yang merupakan satu-satunya pemecah QCQP global yang dapat saya temukan dengan sebanyak lisensi gratis untuk penggunaan akademis. Untungnya, ia memiliki beberapa ikatan Python yang sangat bagus.

Masukan dan keluaran

Lulus daftar jari-jari pada stdin, seperti [5,3,1.5]. Output menunjukkan objective value:daerah persegi panjang, x1, x2dimensi persegi panjang, x3rectangle lagi, x4, x5koordinat pusat lingkaran pertama, x6, x7lingkaran koordinat pusat kedua, dll

Uji kasus

[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

Ini lebih baik daripada solusi OP. Dimensi yang tepat adalah 18 kali 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)

Kasus 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
sumber
Malu yang terakhir memberikan sedikit kesalahan pembulatan, tapi kerja bagus!
Tim
Bagiku [1,2,3,4,5] dapat ditingkatkan dengan membuat jari-jari 3 dan jari-jari 5 jari-jari menyentuh juga, kemudian memutar jari-jari 4 / jari-jari 5 diagonal searah jarum jam searah (jari-jari 1 lingkaran harus dipindahkan keluar dari jalan tetapi ada banyak ruang mati untuk itu. Baik naluri saya dan perhitungan saya menunjukkan bahwa persegi panjang yang tipis dapat mengandung jari-jari 4 / jari-jari 5 lingkaran lebih efisien daripada yang lebih persegi
Level River St
@LevelRiverSt Saya tidak setuju. Bergerak 3 hingga menyentuh 5 akan mendorong 4 menjauh ke kanan (berlawanan arah jarum jam dari 5), tidak membiarkannya bergerak ke kiri (searah jarum jam dari 5). Konfigurasi program saya adalah (7 + 4√3) × (9 + √ (29 + 16√3)) ≈ 13.9282 × 16.5308 ≈ 230.244, sedangkan konfigurasi yang Anda sarankan adalah (30 + 15√3) / 4 × (36 + 3) √5 + 6√15) / 4 ≈ 13.9952 × 16.4865 ≈ 230.732.
Anders Kaseorg