Koordinatni sustav

Koristimo standardni pravokutni koordinatni sustav u ravnini s jedinicom izraženom u centimetrima (cm). List koji Luka ima je u obliku kvadrata stranice duljine \(12\) cm. List je smješten u koordinatni sustav tako da je njegov donji lijevi vrh u ishodištu koordinatnog sustava, a gornji desni u točki \((12 ,12)\). List je podijeljen na centimetarsku mrežu ćelija koju čine kvadrati stranice duljine \(1\) cm. Ćelije su indeksirane parovima \((i,j)\) za \(i,j\in\{0,…,11\}\) pri čemu indeks \((i,j)\) predstavlja kvadrat \([i,i+1]\times[j,j+1]\). Označimo \(Q_{ij} = [i,i+1]\times[j,j+1]\). Početnu poziciju lista s ćelijama nazivamo rezalište. List se može rezati isključivo duž rubova centimetarske mreže ćelija. Svaki izrezani komad lista \(P_r\) (patch) opisan je kao povezani skup ćelija, \[P_r = \bigcup_{(i,j)\in I_r} Q_{ij},\] gdje \(I_r\) predstavlja skup indeksa za komad lista \(P_r\). Rupe na pozornici (stains) označene su zadanim skupom točaka u ravnini (fiksni podatak u skripti).

Funkcija cilja

Vrijeme potrebno za prekrivanje rupa komadima lista ovisi o ukupnom prijeđenom putu u kojeg za svaki pojedini izrezani komad lista \(P_r\) ubrajamo:

• udaljenost između centra mase u rezalištu i centra mase odloženog komada na pozornici (transport komada \(P_r\) iz rezališta na pozornicu),
• udaljenost između centra mase odloženog komada na pozornici i centra mase novog komada predviđenog za rezanje (povratak u rezalište),
• trostruku ukupnu duljinu bridova komada  \(P_r\) (trostruki opseg od \(P_r\)).

Napomena: Centar mase jedinične ćelije \(Q_{ij}\)  je njezino središte \(C_{ij} = (i + 0.5,j+0.5)\), a centar mase komada \(P_r\) je aritmetička sredina (po koordinatama) centara ćelija koje čine \(P_r\). Nakon transporta posljednjeg komada za prekrivanje nije se potrebno vratiti u rezalište. Svaki komad lista se na pozornici može rotirati za kut \(\alpha\), koji predstavlja zakret oko centra mase u odnosu na položaj komada u rezalištu. Kut \(\alpha\) mjeri se u stupnjevima pri čemu pozitivni stupnjevi označavaju obrnuti smjer od smjera kazaljki na satu. Zakret komada lista ne predstavlja dodatni trošak vremena. Rezanje je zahtjevniji proces od samog transporta, stoga faktor 3 u trošku rezanja.

Izazov

Pomozite Luki prekriti zadane rupe na pozornici tako da minimizirate Lukin ukupni prijeđeni put kako je definiran gore.

Format rješenja

Rješenje se u skripti za validaciju opisuje u tekstualnom JSON formatu kako je prikazano u demo verziji. Za potrebe zapisa rješenja, ćelije su numerirane indeksom \(k\in \{0,1,2,...,143\}\). Za ćeliju \(Q_{ij}\) odgovarajući indeks \(k\) računamo po formuli \(k= i + 12 j\).

"parts": [0, 12, 24, 36, 48, 60, 72, 84, 96] - označava povezani komad lista kojeg čine ćelije: 0, 12, 24, 36, 48, 60, 72, 84, 96.

"x": 16.35, "y": 7.4 - označava koordinate centra mase transportiranog komada lista

"alpha": -2 - označava kuta zakreta (u stupnjevima) transportiranog komada lista oko centra mase u odnosu na polazni komad u rezalištu

Demo rješenje:

[
        { "parts": [0, 12, 24, 36, 48, 60, 72, 84, 96],
        "x": 16.35, "y": 7.4, "alpha": -2 },
        { "parts": [7, 8, 9, 10],
        "x": 19.7, "y": 2.3, "alpha": 22 },
        { "parts": [1, 2, 3, 4, 5, 6],
        "x": 18.9, "y": 12.3, "alpha": -15 },
        { "parts": [11, 23, 35, 47, 59, 71, 83, 95, 107, 119, 131, 143],
        "x": 29.5, "y": 6.65, "alpha": 1 },
        { "parts": [22, 34, 46, 58, 70, 82, 94, 106, 118, 130, 142],
        "x": 23.7, "y": 6.9, "alpha": -1 },
        { "parts": [13, 14, 25, 26, 37, 38],
        "x": 26.7, "y": 2.4, "alpha": -10 },
        { "parts": [51, 52, 53, 54, 55, 56, 63, 64, 65, 66, 67, 68, 75, 76, 77, 78, 79, 80, 87, 88, 89, 100],
        "x": 26.6, "y": 8.2, "alpha": -80 },
        { "parts": [15, 16, 17, 18, 19, 27, 28, 29, 30, 31],
        "x": 33.9, "y": 0.8, "alpha": 3 },
        { "parts": [33, 45, 57, 69, 81, 93, 105, 117, 129, 141],
        "x": 31.7, "y": 7.9, "alpha": -3 },
        { "parts": [39, 40, 41, 42, 43],
        "x": 34.1, "y": 12.65, "alpha": -15 }
]

Detaljnije upute o predaji rješenja i evaluacijska skripta nalaze se na stranici Upute za predaju.