transformari-geometrice

Transformări geometrice

** 'Rotaţia':transformari-geometrice#rotatia
** 'Omotetia':transformari-geometrice#omotetia
** 'Desfăşurarea în plan':transformari-geometrice#desfasurarea-in-plan

* 'Aplicaţia 1':transformari-geometrice#aplicatia-1
* 'Aplicaţia 2':transformari-geometrice#aplicatia-2
* 'Aplicaţia 3':transformari-geometrice#aplicatia-3
* 'Aplicaţia 4: PolyLine (TopCoder)':transformari-geometrice#aplicatia-4
* 'Aplicaţia 5 (Olimpiada Letonă, 1997)':transformari-geometrice#aplicatia-5

* '_Aplicaţii_':transformari-geometrice#aplicatia-1
** 'Aplicaţia 1':transformari-geometrice#aplicatia-1
** 'Aplicaţia 2':transformari-geometrice#aplicatia-2
** 'Aplicaţia 3':transformari-geometrice#aplicatia-3
** 'Aplicaţia 4: _PolyLine_ (TopCoder)':transformari-geometrice#aplicatia-4
** 'Aplicaţia 5 (Olimpiada Letonă, 1997)':transformari-geometrice#aplicatia-5
** 'Aplicaţia 6: _Pool_ (Timus)':transformari-geometrice#aplicatia-6
** 'Aplicaţia 7: _NCushion_ (TopCoder)':transformari-geometrice#aplicatia-7
** 'Aplicaţia 8':transformari-geometrice#aplicatia-8
** 'Aplicaţia 9':transformari-geometrice#aplicatia-9
** 'Aplicaţia 10':transformari-geometrice#aplicatia-10
** 'Aplicaţia 11':transformari-geometrice#aplicatia-11
** 'Aplicaţia 12':transformari-geometrice#aplicatia-12
** 'Aplicaţia 13':transformari-geometrice#aplicatia-13
** 'Aplicaţia 14':transformari-geometrice#aplicatia-14
** 'Aplicaţia 15':transformari-geometrice#aplicatia-15
** 'Aplicaţia 16':transformari-geometrice#aplicatia-16
** 'Aplicaţia 17':transformari-geometrice#aplicatia-17
** 'Aplicaţia 18':transformari-geometrice#aplicatia-18

h2(#introducere). Introducere

h3. Rezolvare:

Folosim aceeaşi idee: ducem simetricul punctului $A$, notat cu $A’$, faţă de dreapta $d{~1~}$ şi simetricul punctului $B$ notat cu $B’$ faţă de dreapta $d{~2~}$. Orice puncte $M$ şi $N$ am alege, avem că $AM + MN + NB = A’M + MN + NB$. Pentru a minimiza suma $A’M + MN + NB’$ trebuie ca $M$ şi $N$ să fie intersecţiile segmentului $A’B’$ cu semidreptele $d{~1~}$ şi $d{~2~}$.

Folosim aceeaşi idee: ducem simetricul punctului $A$, notat cu $A’$, faţă de dreapta $d{~1~}$ şi simetricul punctului $B$ notat cu $B’$ faţă de dreapta $d{~2~}$. Orice puncte $M$ şi $N$ am alege, avem că $AM + MN + NB = A’M + MN + NB’$. Pentru a minimiza suma $A’M + MN + NB’$ trebuie ca $M$ şi $N$ să fie intersecţiile segmentului $A’B’$ cu semidreptele $d{~1~}$ şi $d{~2~}$.

h2(#aplicatia-3). Aplicaţia 3

Luăm un punct $M$ pe baza $BC$ a triunghiului $ABC$, un punct $P$ pe latura $AB$ şi un punct $N$ pe latura $AC$. Dacă avem $M’$ simetricul lui $M$ faţă de $AB$ şi $M’’$ simetricul lui $M$ faţă de $AC$, atunci $MN + NP + PM = M’’N + NP + PM’$. Ca să minimizăm această sumă, punctele $P$ şi $N$ trebuie să fie la intersecţia segmentului $M’M’’$ cu laturile $AB$, respectiv $AC$. Perimetrul triunghiului $MNP$ va fi egal cu lungimea segmentului $M’M’’$. Observăm că unghiul $M’AM’’$ are măsura egală cu $2 * măsura unghiului BAC$ şi că triunghiul $M’AM’’$ e isoscel de latură egală cu $AM$. Pentru ca $M’M’’$ să aibă lungimea minimă trebuie ca $AM$ să fie cât mai scurt. Acest segment este minim atunci când $M$ este piciorul înalţimii din $A$. La fel putem să deducem că $N$ este piciorul înălţimii din $B$, iar $P$ este piciorul înălţimii din $C$. Astfel, soluţia de perimetru minim este triunghiul ortic.

h2(#aplicatia-4). Aplicaţia 4: 'PolyLine':http://www.topcoder.com/stat?c=problem_statement&pm=4509 (TopCoder)

h2(#aplicatia-4). Aplicaţia 4: '_PolyLine_':http://www.topcoder.com/stat?c=problem_statement&pm=4509 (TopCoder) X

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$.

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)

h2(#aplicatia-6). Aplicaţia 6: '_Pool_':http://acm.timus.ru/problem.aspx?space=1&num=1258 (Timus)

!> transformari-geometrice?aplicatie-6.1.png 80%!

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.

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 pereţii. De exemplu, în imagine pereţii sunt atinşi în ordinea $NVEVES$. Numărul de coliziuni 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.

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.

h2(#aplicatia-7). Aplicaţia 7: 'NCushion':http://www.topcoder.com/stat?c=problem_statement&pm=1963 (TopCoder)

h2(#aplicatia-7). Aplicaţia 7: '_NCushion_':http://www.topcoder.com/stat?c=problem_statement&pm=1963 (TopCoder)

bq. Pe o masă de biliard de dimensiuni $2000 x 1000$ sunt aşezate două bile la coordonate întregi. Se cere să se determine numărul de posibilităţi de lovire a primei bile, astfel ca ea să lovească exact de $N$ ori manta $(1 ≤ N ≤ 500)$ şi apoi să lovească cea de a doua bilă. Mişcarea bilei se consideră ideală, iar dacă bila loveşte un colţ se consideră că s-au atins două mante şi bila se va mişca pe aceiaşi direcţie în sens opus.

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.

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)

h2(#aplicatia-12). Aplicaţia 12 (TopCoder)

bq. Pe partea frontală a unui zgârie-nor foarte înalt, ce are forma unui paralelipiped, cu baza un pătrat de latura $200$ de metri, este situat un păianjen. Acesta vrea să mănânce o muscă situată pe faţa din dreapta a zgârie-norului. Ştiind coordonatele păianjenului şi ale muştei vi se cere să determinaţi drumul cel mai scurt pe care îl poate face păianjenul ca să mănânce musca iar întreaga deplasare a lui să fie pe suprafaţa zgârie-norului (coordonatele gângăniilor se măsoară relativ la colţul stânga sus al feţei pe care se află fiecare).

bq. Pe partea frontală a unui zgârie-nor foarte înalt, ce are forma unui paralelipiped, cu baza un pătrat de latura $200$ de metri, este situat un păianjen. Acesta vrea să mănânce o muscă situată pe faţa din dreapta a zgârie-norului. ştiind coordonatele păianjenului şi ale muştei vi se cere să determinaţi drumul cel mai scurt pe care îl poate face păianjenul ca să mănânce musca iar întreaga deplasare a lui să fie pe suprafaţa zgârie-norului (coordonatele gângăniilor se măsoară relativ la colţul stânga sus al feţei pe care se află fiecare).

h3. Rezolvare:

h2(#aplicatia-17). Aplicaţia 17: Texan (Baraj ONI, 2005)

!> transformari-geometrice?aplicatie-17.1.png 75%!
 

bq. Se dă un poligon convex de $N$ vârfuri $(3 ≤ N ≤ 700)$. Se cere să se determine un triunghi echilateral cu vârfurile aparţinând laturilor poligonului convex.
h3. Rezolvare:

Luăm un punct $O$ pe o latură a poligonului, rotim întreg poligonul în jurul acestui punct 60 de grade în sens trigonometric. Poligonul rotit va intersecta poligonul îniţial într-un nou punct B. Acest punct B îl rotim în jurul lui O cu 60 de grade în sens orar, rezultatul este un punct B’ care evident aparţine poligonului iniţial. Acum triunghiul OBB’ este echilateral pentru că OB = OB’ şi masura unghiului BOB’ este de 60 de grade. Menţionăm că aceasta a fost una dintre cele mai dure probleme de la selectia lotului de anul acesta.O rezolvare de complexitate O(N^2) a fost de ajuns pentru ca autorul să obţină punctajul maxim la ONIbyNet, dar facem observaţia că intersecţia a două poligoane convexe se poate face în complexitate O(N).
 

Luăm un punct $O$ pe o latură a poligonului. Rotim întreg poligonul în jurul acestui punct $60$ de grade în sens trigonometric. Poligonul rotit va intersecta poligonul iniţial într-un nou punct $B$. Acest punct $B$ îl rotim în jurul lui $O$ cu $60$ de grade în sens orar. Rezultatul este un punct $B’$ care evident aparţine poligonului iniţial. Acum triunghiul $OBB’$ este echilateral pentru că $OB = OB’$ şi măsura unghiului $BOB’$ este de $60$ de grade. Menţionăm că aceasta a fost una dintre cele mai dure probleme de la selecţia lotului de anul acesta. O rezolvare de complexitate $O(N^2^)$ a fost de ajuns pentru punctajul maxim, dar facem observaţia că intersecţia a două poligoane convexe se poate face în complexitate $O(N)$.
 
h2(#aplicatia-18). Aplicaţia 18: dotNet (.campion, 2004)
 
bq. Se dau $N$ puncte în planul euclidian prin coordonatele lor, numere întregi. Apoi se efectuează $M$ operaţii asupra tuturor punctelor, într-o ordine dată $(1 ≤ N ≤ 100 000, 0 ≤ M ≤ 10 000)$. O operaţie poate fi de două tipuri: de translaţie sau de rotaţie. Într-o operaţie de rotaţie, punctele sunt rotite în jurul originii cu un anumit număr de grade în sens trigonometric. Într-o operaţie de translaţie, originea este mutată în alt punct relativ la originea curentă şi coordonatele celorlalte puncte sunt modificate astfel încât să reprezinte aceleaşi puncte relativ la noua origine. Scrieţi un program care calculează coordonatele tuturor punctelor după cele $M$ operaţii.
 
h3. Rezolvare:
 
Folosim scrierea operaţiilor de translaţie si rotaţie ca produs de  matrici. Dacă vrem să rotim punctul $(x, y)$ în jurul punctului de coordonate $(0, 0)$ după un unghi <tex> \alpha </tex> atunci putem scrie:
 
<tex> \left[ \begin{array}{c} x_1 \\ y_1 \\ 1 \end{array} \right] = \begin{bmatrix} cos \alpha & -sin \alpha & 0 \\ sin \alpha & cos \alpha & 0 \\ 0 & 0 & 1 \end{bmatrix} \times \left[ \begin{array}{c} x \\ y \\ 1 \end{array} \right] </tex>
 
Iar translaţia o putem scrie ca:
 
<tex> \left[ \begin{array}{c} x_2 \\ y_2 \\ 1 \end{array} \right] = \begin{bmatrix} 1 & 0 & dx \\ 0 & 1 & dy \\ 0 & 0 & 1 \end{bmatrix} \times \left[ \begin{array}{c} x \\ y \\ 1 \end{array} \right] </tex>
 
Astfel transformarea pentru un punct devine un produs de matrici care la sfârşit se înmulţeşte cu un vector ce reprezintă coordonatele punctului pe care vrem să îl transformăm. Pentru că transformarea compusă este aceeaşi pentru fiecare dintre cele $N$ puncte, determinăm matricea care o reprezintă o singură dată şi apoi o putem aplica pe rând fiecărui punct. Algoritmul are complexitatea $O(N + M)$.
Menţionăm că o problemă similară apare pe SGU sub numele de wizards, diferenţa fiind că acolo operaţiile sunt în spaţiul tridimensional, dar rezolvarea este aproape identică.
 
 
h2(#bibliografie). Bibliografie
 
# Nicolescu, Boskoff, _Probleme practice de geometrie_, Ed. Tehnică, Bucureşti, 1990
# 'Cut the Knot':http://www.cut-the-knot.org
# 'Timus':http://acm.timus.ru/
# 'UVa':http://uva.onlinejudge.org/
# 'TopCoder':http://www.topcoder.com/tc
# 'SGU':http://acm.sgu.ru
# Dijkstra’s EWDs