Tehnički opis problema i format rješenja

Tekst izazova:

Tvrtka "Munjovoz" bavi se razvojem električnih vozila. U okviru optimizacije novog modela imaju zahtjev za što gušćim pakiranjem ukupno 200 baterija različitih veličina u jedan spremnik kvadratnog presjeka. Poprečni presjek svake baterije je eliptičkog oblika. Presjek 39 baterija ima poluosi veličine 40 mm i 20 mm, dok presjek 161 baterije ima poluosi veličine 20 mm i 10 mm. Baterije se pakiraju uspravno te se mogu dodirivati s bočne strane, ali se ne smiju slagati jedna na drugu. Zbog izvedbene preciznosti stroja koji puni spremnik s baterijama dozvoljene su samo diskretne vrijednosti položaja baterija i to tako da je najmanji mogući pomak baterije duž koordinatnih osi 1/1000 mm te najmanji kut rotacije 1/1000 stupnja. Pomozite inženjerima tvrtke "Munjovoz" pronaći pakiranje svih baterija u spremnik što manjeg kvadratnog poprečnog presjeka.

 

Detaljniji opis problema:

U zadatku se traži naći pakiranje 200 elipsi bez preklapanja u kvadrat što manje površine. 39 elipsi ima poluosi veličine 40 mm i 20 mm, a 161 ih ima poluosi veličine 20 mm i 10 mm. U koordinatnom sustavu \(xOy\) svaka elipsa jednoznačno je određena (vidi sliku):

  • središtem s koordinatama \((x_c, y_c)\in \mathbb{R}^2\),
  • duljinama poluosi \((a,b)\), pri čemu je \(a>b>0\),
  • kutom otklona \(\theta\in [0,\pi)\) dulje poluosi elipse od pozitivnog dijela \(x\)-osi.
     

 

U slanju rješenja, za svaku od 200 elipsi šalje se gornjih 5 brojeva. Vidi detaljnije upute za slanje rješenja. Traženi kvadrat koji opisuje sve elipse ima stranice paralelne s koordinatnim osima i prilikom valorizacije rješenja neće se uzimati u obzir kvadrati kojima stranice nisu paralelne s koordinatnim osima. Vidi sliku niže.

Zbog izvedbene preciznosti stroja koji puni spremnik s baterijama u optimizacijskom postupku dozvoljene su samo diskretne vrijednosti položaja elipsi i to tako da je najmanji mogući pomak elipse duž koordinatnih osi 1/1000 mm, a najmanji kut otklona 1/1000 stupnja. Preciznije, koordinate središta elipsi su cjelobrojni višekratnici 1/1000 mm, dok je kut otklona cjelobrojni višekratnik 1/1000 stupnja.

 

Format rješenja

Kako su pozicije elipsi diskretne u mjernim jedinicama 1/1000 mm (za pomak) i 1/1000 stupnja (za rotaciju), geometrija rješenja opisana je cijelim brojevima (tip podataka integer). Preciznije, \(x_c = X_c/1000\), \(y_c = Y_c/1000\), \(a=A/1000\), \(b=B/1000\) i \(\theta = \Theta/1000\), gdje su \(X_c\), \(Y_c\), \(A\), \(B\) i \(\Theta\) cijeli (integer) brojevi. U CSV datoteci koja opisuje pakiranje elipsi, za svaku od 200 elipsi upisuju se cijeli brojevi \(X_c\), \(Y_c\), \(A\), \(B\) i \(\Theta\). Vidi predložak rješenja.