p=. !transformari-geometrice?aplicatie-4.1.png 70%!
!> transformari-geometrice?aplicatie-4.2.png 70%!
h3. Rezolvare:
!< transformari-geometrice?aplicatie-4.2.png 70%!
Este evident că o soluţie optimă va fi formată din cinci segmente. Putem încerca toate ordinele posibile ale drumului liniei frânte, fiind $4! = 24$ asemenea ordini. Pentru fiecare ordine căutăm drumul optim. Acesta poate fi găsit folosind trucul prezentat în problemele anterioare. Să luăm un exemplu: pentru punctele $A(1, 2)$ şi $B(1,3)$ şi dreptunghiul de dimensiuni $4$ şi $3$, luăm punctele $M, N, P, Q$ pe laturile din stânga, jos, dreapta respectiv sus ale dreptunghiului astfel încât să minimizăm suma $AM + MN + NP + PQ + QB$. Acum, vom duce simetricul lui $A$, notat cu $A’$, faţă de latura din stânga şi simetricul lui $B$, notat cu $B’$, faţă de latura de sus. Avem că $AM = A’M$ şi $QB = QB’$. Deci, ca să minimizăm suma $AM + MN + NP + PQ + QB$ trebuie să minimizăm suma $A’M + MN + NP + PQ + QB’$. Vom duce simetricul lui $A’$, notat prin $A’’$, faţă de latura de jos, şi simetricul lui $B’$, notat prin $B’’$, faţă de latura din dreapta. Avem că $A’M + MN <= A’’N$ şi că $PQ + QB’ <= QB’’$, deci obţinem că pentru a minimiza suma $AM + MN + NP + PQ + QB$ trebuie să minimizăm suma $A’’M + MN + NB’’$. Putem realiza acest obiectiv dacă $M$ şi $N$ vor fi intersecţiile segmentului $A’’B’’$ cu latura de jos, respectiv latura din dreapta a dreptunghiului, iar soluţia este exact distanţa de la $A’’$ la $B’’$.
h2(#aplicatia-5). Aplicaţia 5 (Olimpiada Letonă, 1997)
!< transformari-geometrice?aplicatie-5.1.png 70%!
!> transformari-geometrice?aplicatie-5.2.png 70%!
bq. Laturile unui teren dreptunghiular de biliard de dimensiuni $43 x 73$ sunt etichetate cu literele $A, R, Z, D$. O bilă $B$ (dimensiunile căreia pot fi ignorate) este plasată în interiorul acestui teren la $13$ centimetri distanţă de latura $R$ şi la $29$ de centimetri distanţă de latura $D$. Un jucător îşi pune tacul pe latura $R$ la un punct ce e situat la $K$ centimetri distanţă de latura $D$ şi loveşte direct bila $B$. Bila se mişcă drept şi dacă e cazul loveşte marginile terenului. Mişcarea bilei se supune legilor fizicii, astfel, când bila se loveşte de margine ea va avea o traiectorie simetrică cu traiectoria iniţială faţă de dreapta perpendiculară pe margine în punctul de impact. O parte din traiectoria bilei o puteţi vedea în figură. Problema esta pentru un număr fix $K (0 ≤ K ≤ 73)$ şi $N (0 ≤ N ≤ 10^9^)$. Să se determine distanţa bilei faţă de latura $R$ şi distanţa faţă de latura $D$, după ce bila s-a deplasat exact $N$ centimetri.
!> transformari-geometrice?aplicatie-5.3.png 65%!
h3. Rezolvare:
O rezolvare bazată pe simularea mişcării bilei pare anevoioasă, iar din cauza faptului că $N$ poate fi foarte mare, acest algoritm nu este eficient. O rezolvare elegantă este următoarea. Întâi umplem planul cu o grilă infinită de dreptunghiuri de dimensiuni $43 x 73$. Dacă am lăsa ca bila să îşi continue mişcarea şi am ignora prima lovire a marginii, în terenul adiacent, atunci traiectoria bilei ar fi de la trecerea marginii simetrică cu traiectoria normală a bilei, deci ar fi ca şi cum am reflecta întreaga tablă. Acest fenomen se repetă de fiecare dată când atingem o margine. Astfel, dacă ducem un segment pe direcţia de deplasare a bilei, ce pleacă din $B$, de lungime $N$, şi se termină în $C$ atunci putem vedea în ce dreptunghi este el inclus, şi în funcţie de acest dreptunghi să transformăm punctul $C$ în poziţia finală a bilei în dreptunghiul iniţial.
h2(#aplicatia-6). Aplicaţia 6: 'Pool':http://acm.timus.ru/problem.aspx?space=1&num=1258 (Timus)
!transformari-geometrice?aplicatie-5.1.png 70%!
!< transformari-geometrice?aplicatie-6.1.png 70%!
bq. Programatorului Vasile îi place să se plimbe prin biroul lui dreptunghiular. El începe drumul din locul unde este situat biroul lui şi se plimbă până când crede că ar trebui să se apuce de lucru din nou. Drumul lui urmează legea de mişcare dată de „unghiul de incidenţă este egal cu unghiul de reflexie”. Vasile se mişcă de la zid la zid în linie dreaptă. Şeful direct al lui Vasile este interesat cât timp pierde acesta în plimbările lui. Este uşor să aflăm timpul, împărţind distanţa parcursă la viteza medie a lui Vasile (aceasta a fost deja calculată de şef), deci trebuie să se afle distanţa parcursă. Se ştie ordinea în care au fost atinşi pereţii întrucât Vasile, fiind neatent, se loveşte de pereţi şi astfel se aud bufniturile în fiecare zid. Se dau dimensiunile camerei lui Vasile: $W$ şi $D (0 ≤ W, D ≤ 100)$, poziţia iniţială, poziţia finală şi secvenţa de litere $N, S, E, V$ care este ordinea în care sunt atinşi peretii. De exemplu, în imagine pereţii sunt atinşi în ordinea $NVEVES$. Numărul de coliziui nu depăşeste $1000$, poziţiile iniţiale şi finale nu se află pe marginile dreptunghiului, iar drumul lui Vasile nu va trece prin vreun colţ al încăperii.
!transformari-geometrice?aplicatie-5.2.png 70%!
h3. Rezolvare:
Precum în problema anterioară, când Vasile atinge un perete mişcarea lui se oglindeşte faţă de mişcarea normală. Vom procesa fiecare instrucţiune din şirul în care e prezentată ordinea atingerii pereţilor. O instrucţiune va însemna o reflexie a dreptunghiului curent şi a punctului destinaţie al lui Vasile. După ce vom procesa toate coliziunile obţinem dreptunghiul final şi punctul de destinaţie transformat în interiorul acestui dreptunghi. Acum linia frântă care unea punctul de start s-a transformat într-un segment de dreaptă între punctul de start şi imaginea punctului final după ce s-a realizat asupra lui seria de transformări.
!transformari-geometrice?aplicatie-5.3.png 70%!
O rezolvare bazată pe simularea mişcării bilei pare anevoioasă, iar din cauza faptului că $N$ poate fi foarte mare, acest algoritm nu este eficient. O rezolvare elegantă este următoarea. Întâi umplem planul cu o grilă infinită de dreptunghiuri de dimensiuni $43 x 73$. Dacă am lăsa ca bila să îşi continue mişcarea şi am ignora prima lovire a marginii, în terenul adiacent, atunci traiectoria bilei ar fi de la trecerea marginii simetrică cu traiectoria normală a bilei, deci ar fi ca şi cum am reflecta întreaga tablă. Acest fenomen se repetă de fiecare dată când atingem o margine. Astfel, dacă ducem un segment pe direcţia de deplasare a bilei, ce pleacă din $B$, de lungime $N$, şi se termină în $C$ atunci putem vedea în ce dreptunghi este el inclus, şi în funcţie de acest dreptunghi să transformăm punctul $C$ în poziţia finală a bilei în dreptunghiul iniţial.
