bq. Se consideră un dreptunghi cu colţurile de coordonate $(0, 0)$ , $(a, 0)$, $(a, b)$, $(0, b)$. Mai considerăm două puncte $A$ şi $B$ de coordonate $(x{~1~}, y{~1~})$ şi $(x{~2~}, y{~2~})$ în interiorul dreptunghiului. Se cere să se determine lungimea minimă a unei linii frânte ce porneşte din $A$ ajunge în $B$ şi intersectează fiecare latură a dreptunghiului. În figura de mai jos, avem un dreptunghi de dimensiuni $4 x 3$ şi trei posibilităţi de a plasa două puncte în interiorul dreptunghiului, împreună cu soluţiile optime. Rezultatele pentru cele trei exemple sunt: $7.8102$, $8.6023$, respectiv $9.4339$.
!transformari-geometrice?aplicatie-4.1.png 70%!
p=. !transformari-geometrice?aplicatie-4.1.png 70%!
h3. Rezolvare:
!transformari-geometrice?aplicatie-4.2.png 70%!
!< 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)
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.1.png 70%!
!transformari-geometrice?aplicatie-5.2.png 70%!
h3. Rezolvare:
!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.
