Biorąc pod uwagę listę okręgów, wypisz obszar najmniejszego zawierającego prostokąt

28

Otrzymasz listę promieni, musisz wyprowadzić obszar najmniejszego prostokąta, w którym się zmieszczą.

Na przykład, biorąc pod uwagę listę, [5,3,1.5]którą wypiszesz 157.460.

To jest obrazek:

Szerokość wynosi 15.7460, a wysokość to 10, więc obszar wynosi 157.460

Zasady:

  • Otrzymujesz listę za pomocą argumentu stdin lub funkcji, a odpowiedź podajesz przez stdout lub return funkcji.

  • Promienie będą miały najwyżej 2 miejsca po przecinku.

  • Lista będzie miała długość od 2 do 6.

  • Dane wyjściowe powinny być dokładne z dokładnością do 3 miejsc po przecinku lub więcej.

  • Jeśli potrzebujesz, π = 3,1416.

Przypadki testowe:

  • [5,3,1.5] = 157.460

  • [9,4,8,2] = 733.431- pracuję tutaj .

  • [18,3,1] = 1296.000

Najkrótszy kod w bajtach wygrywa.

code-golf math optimization Tim
źródło
Powiązane
DJMcMayhem
1
nie widzę obiektywnego kryterium wygranej
Maltysen
to jedna z naszych najważniejszych zasad
Maltysen
2
@Tim Większość to golf golfowy, którego celem jest zakodowanie go w jak najmniejszej liczbie bajtów. Myślę, że byłoby to dobre wyzwanie dla golfa, ponieważ ma dokładną specyfikację.
xnor
Polecam pozbyć się warunku „zaokrąglonego, nie obciętego”, ponieważ jest on powiązany z zadaniem, a niektóre języki mogą to zrobić, podczas gdy inne wymagają dodatkowego kodowania, aby to się stało. Nie jestem pewien, czy zamierzasz wypisywać więcej niż 3 miejsca po przecinku, ale proponuję to również pozwolić.
xnor

Odpowiedzi:

16

Python 2 + PySCIPOpt , 267 bajtów

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

Jak to działa

Piszemy problem w następujący sposób: zminimalizuj c ponad zmiennymi a , b , c , x 1 , y 1 ,…, x n , y n , gdzie

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

Oczywiście używamy zewnętrznej biblioteki optymalizującej te ograniczenia, ale nie możesz po prostu podać ich do żadnego starego optymalizatora - nawet Mathematica NMinimizeutknęła na lokalnych minimach dla tych małych przypadków testowych. Jeśli przyjrzysz się uważnie ograniczeniom, zobaczysz, że stanowią one kwadratowy program kwadratowy , a znalezienie globalnego optimum dla niewypukłego QCQP jest trudne. Potrzebujemy więc niesamowicie potężnej magii. Wybrałem przemysłowy program do rozwiązywania problemów SCIP , który jest jedynym globalnym programem do rozwiązywania problemów QCQP, jaki udało mi się znaleźć, oferując darmową licencję do użytku akademickiego. Na szczęście ma kilka bardzo fajnych powiązań w języku Python.

Wejście i wyjście

Przekaż listę promieni na stdin, jak [5,3,1.5]. Na wyświetlaczu wyjściowe objective value:obszar prostokąt x1, x2prostokąt wymiary, x3prostokątny obszar ponownie x4, x5najpierw współrzędne środka okręgu, x6, x7drugie koło współrzędne środka itp

Przypadki testowe

[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

To lepsze niż rozwiązanie PO. Dokładne wymiary to 18 na 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)

Przypadki bonusowe

[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
źródło
Wstyd ten ostatni powoduje drobny błąd zaokrąglenia, ale fajna robota!
Tim
Wydaje mi się, że [1,2,3,4,5] można poprawić, dotykając również promienia 3 i promienia 5, a następnie lekko obracając promień 4 / promień 5 po przekątnej zgodnie z ruchem wskazówek zegara (promień 1 okrąg musiałby zostać odsuniętym na bok, ale jest na to mnóstwo martwej przestrzeni. Zarówno mój instynkt, jak i moje obliczenia wskazują, że długi, cienki prostokąt może zawierać promień 4 / promień 5 kół bardziej efektywnie niż kwadratowy
Level River St
@LevelRiverSt Nie zgadzam się. Przesunięcie 3 w górę, by dotknąć 5, popchnęłoby 4 w prawo (przeciwnie do ruchu wskazówek zegara od 5), nie pozwalając, by przesunęło się w lewo (zgodnie z ruchem wskazówek zegara od 5) Konfiguracja mojego programu to (7 + 4√3) × (9 + √ (29 + 16√3)) ≈ 13,9282 × 16,5308 ≈ 230,244, podczas gdy sugerowana konfiguracja to (30 + 15√3) / 4 × (36 + 3 √5 + 6√15) / 4 ≈ 13,9952 × 16,4865 ≈ 230,732.
Anders Kaseorg