!> transformari-geometrice?aplicatie-8.2.png 70%!

O rezolvare posibilă ar fi să pornim cu o lovitură de un unghi fixat şi să vedem dacă ajunge în poartă, iar apoi să creştem unghiul loviturii puţin câte puţin. Prin folosirea unor consideraţii de simetrie putem rezolva problema mai uşor şi mai eficient. Oglindim terenul împreună cu toţi jucătorii. Astfel, transformăm lovitura din două segmente în unul singur care trece prin dreapta de simetrie. Acum, luăm fiecare punct lateral al jucătorilor, fiecare punct lateral al imaginii reflectate ale jucătorilor şi punctele porţii reflectate, şi unim aceste puncte cu punctul de unde jucătorul va lovi pucul. Verificăm care dintre aceste drepte dacă sunt rotite foarte puţin la dreapta sau la stânga intersectează imaginea porţii reflectate şi nu intersectează segmentele ce reprezintă jucătorii sau imaginea lor reflectată. Astfel, soluţia noastră are complexitatea $O(N^2^)$ unde $N$ este numărul de jucători, pentru că pentru fiecare dintre cele $4N + 2$ raze trebuie să verificăm intersecţia cu $2N + 1$ segmente. Pe acestă idee putem realiza o soluţie în $O(N log N)$ folosind o linie de baleiere care trece prin punctul iniţial si se mişcă circular în jurul lui.
 
h2(#aplicatia-9). Aplicaţia 9: 'Poligon 2':problema/poligon2 (infoarena)
 
bq. Se dau coordonatele mijloacelor laturilor unui poligon nu neapărat convex şi care se poate autointersecta. Se cere să se determine coordonatele vârfurilor poligonului.
 
h3. Rezolvare:
 
Considerăm că poligonul are $N$ vârfuri. Rezolvăm problema întâi pentru $N$ par. Luăm primul vârf al poligonului, şi îi determinăm simetricul faţă de primul mijloc de latură. Astfel găsim al doilea vârf. Dacă luăm al doilea vârf printr-o simetrie îl obţinem pe al treilea ş.a.m.d. Deci prin $N$ simetrii obţinem din nou primul punct. Cum $N$ este par fiecare două simetrii compuse sunt o translaţie, deci avem o serie de translaţii care se compun într-una care duce punctul iniţial în punctul iniţial. Aşa cum am vazut la partea teoretică translaţia are un punct fix doar dacă ea e translaţie trivială. Translaţia fiind trivială, putem porni cu orice punct din plan şi să obţinem celelalte $N + 1$ puncte din poligon ca şi rezultate ale simetriilor aplicate succesiv. În cazul în care $N$ e impar transformarea explicată mai sus are ca rezultat compunerea între o translaţie şi o simetrie, compunere care aşa cum puteţi verifica are ca rezultat o simetrie de alt centru. Dar punctul iniţial este transformat în acelaşi punct, deci el trebuie să fie centrul de simetrie al transformării compuse. Şi, atunci luăm un punct oarecare $P$ în plan, efectuăm cele $N$ transformări asupra lui şi obţinem un punct $P’$. Primul punct al poligonului va fi mijlocul acestui segment.
 
h2(#aplicatia-10). Aplicaţia 10: 'Dmg':problema/dmg (Stelele Informaticii 2005, infoarena)
 
bq. Se dau $N (1 ≤ N ≤ 1500)$ puncte de coordonate întregi. Să se determine numărul de axe de simetrie al sistemului de puncte.
 
h3. Rezolvare:
 
Axele de simetrie ale sistemului de puncte trebuie să fie şi axe de simetrie pentru poligonul ce reprezintă înfăşurătoarea convexă a acestor puncte. Dacă vrem să găsim axele de simetrie ale unui poligon convex, observăm că dacă el are număr par de vârfuri, atunci trebuie ca acestea sau să fie mediatoare pentru o latură a poligonului, sau să treacă prin două vârfuri. Dacă el are număr impar de laturi atunci axele de simetrie trebuie să fie mediatoare pentru o latură şi să treacă printr-un punct al poligonului. Astfel, după calcularea în $O(N log N)$ a înfăţurătorii convexe, putem afla în timp $O(N)$ care sunt candidate la axa de simetrie a poligonului. Verificarea faptului dacă o dreaptă este axă de simetrie pentru un set de puncte o putem face în $O(N)$ folosindu-ne de o tabelă de dispersie. Algoritmul de determinare a axelor de simetrie are complexitatea finală $O(N^2^)$.
 
h2(#aplicatia-11). Aplicaţia 11: (ONM 1997, clasa a VIII-a)
 
bq. Se dă un paralelipiped $ABCDEFGH$, cu $AB = 5$, $BC = 4$, $AE = 3$. Se cere să determinăm poziţia unui punct $M$ ce aparţine segmentului $BF$ cu proprietatea că suma $AM + MG$ este minimă.
 
!> transformari-geometrice?aplicatie-11.1.png 70%!
 
h3. Rezolvare
 
!> transformari-geometrice?aplicatie-11.2.png 70%!
 
Pentru această problemă ne putem imagina o soluţie analitică în care vrem să minimizăm funcţia $AM + MG$ care depinde de coordonata $y$, dar o asemenea rezolvare nu ar fi fost accesibilă unui elev de clasa a VIII-a. O soluţie elegantă şi simplă este următoarea. Desfăşurăm în plan feţele $ABFE$ şi $BCGD$. Astfel se formează dreptunghiul $ACGE$, unde $AC = 9$ şi $AE = 3$. Acum este clar că punctul $M$ trebuie să fie intersecţia diagonalei $AG$ cu $FB$. De aici putem găsi foarte uşor că $BM = 5/3$.

O rezolvare posibilă ar fi să pornim cu o lovitură de un unghi fixat şi să vedem dacă ajunge în poartă, iar apoi să creştem unghiul loviturii puţin câte puţin. Prin folosirea unor consideraţii de simetrie putem rezolva problema mai uşor şi mai eficient. Oglindim terenul împreună cu toţi jucătorii. Astfel, transformăm lovitura din două segmente în unul singur care trece prin dreapta de simetrie. Acum, luăm fiecare punct lateral al jucătorilor, fiecare punct lateral al imaginii reflectate ale jucătorilor şi punctele porţii reflectate, şi unim aceste puncte cu punctul de unde jucătorul va lovi pucul. Verificăm care dintre aceste drepte dacă sunt rotite foarte puţin la dreapta sau la stânga intersectează imaginea porţii reflectate şi nu intersectează segmentele ce reprezintă jucătorii sau imaginea lor reflectată. Astfel, soluţia noastră are complexitatea $O(N^2^)$ unde $N$ este numărul de jucători, pentru că pentru fiecare dintre cele $4N + 2$ raze trebuie să verificăm intersecţia cu $2N + 1$ segmente. Pe acestă idee putem realiza o soluţie în $O(N log N)$ folosind o linie de baleiere care trece prin punctul iniţial si se mişcă circular în jurul lui.