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, Topcoder':http://www.topcoder.com/stat?c=problem_statement&pm=1963

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.

Soluţia foloseşte ideea de mai sus de a reflecta tabla de biliard împreună cu poziţia celei de a doua bile. Aşa cum am văzut în problema anterioară, fiecare şir de atingeri al mantelor ne dă exact un mod în care prima bilă o poate lovi pe cea de a doua. Dacă ştim în ce dreptunghi reflectat vrem să lovim bila a doua, fixând acest dreptunghi, avem o direcţie fixată şi un şir de mante fix pe care le va atinge bila dacă va fi lovită în acea direcţie. În figură avem cazul în care trebuie să lovim exact două mante înainte să atingem a doua bilă.

În desen am colorat cu negru bila iniţială şi cu alb a doua bilă şi imaginile ei. Cu linie punctată am desenat traiectoriile care ar fi atins bila a doua fără a atinge de două ori manta şi cu linie neagră direcţiile pe care manta ar fi atinsă exact de două ori. Observăm că pentru a atinge manta de $N$ ori o bilă trebuie să intre în $N$ alte dreptunghiuri. Deci, asociem poziţiilor dreptunghiurilor un sistem de coordonate în care dreptunghiul iniţial are coordonatele $(0, 0)$. Pentru ca bila să atingă exact $N$ mante, coordonatele $(x, y)$ ale dreptunghiului trebuie să satisfacă egalitatea $|x| + |y| = N$. Mai trebuie să avem grijă ca drumul bilei care atinge $N$ mante să nu atingă a doua bilă înainte de atingerea tuturor mantelor. Aceste observaţii ne duc la următoarea soluţie: pentru toate dreptunghiurile $(x, y)$, care satisfac proprietatea $|x| + |y| < N$, păstrăm într-o structură de date (structura preferată de autor ar fi un 'tabel de dispersie':tabele-hash-prezentare-detaliata) vectorul asociat direcţiei pe care ar fi trebuit lovită prima bilă pentru a ajunge la imaginea celei de a doua bile din acest dreptunghi. Apoi, pentru fiecare dreptunghi pentru care $|x| + |y| = N$, dacă direcţia asociată lui nu este în structura de date, incrementăm numărul de soluţii. Această rezolvare are complexitatea $O(N^2^ log N)$ pentru că normalizarea unei direcţii implică folosirea 'algoritmului lui Euclid':problema/euclid2 ce are complexitate $O(log N)$.
 
h2(#aplicatia-8). Aplicaţia 8: 'PuckShot':http://www.topcoder.com/stat?c=problem_statement&pm=2411&rd=4750 (TopCoder)
 
bq. Un jucător de hockey stângaci are o mişcare în care de la mijlocul terenului izbeşte pucul de marginea terenului care apoi întră în spaţiul porţii. Terenul este de $3000$ de centimetri lăţime. Distanţa între linia de mijloc şi linia de gol este de $1733$ de centimetri. Poarta este centrată pe linia de gol şi are dimensiunea de $183$ de centimetri. Când jucătorul loveşte, puc-ul se va lovi de marginea terenului şi apoi va ricoşa simetric în poartă. Pucul şi stâlpii porţii vor fi considerate puncte. Pe gheaţă vor fi cel mult nouă jucători care vor fi modelaţi ca segmente orizontale de lungime $50$ centimetri. Pentru ca lovitura să aibă succes, traiectoria ei nu trebuie să intersecteze niciun jucător. Pentru simplitate, puteţi presupune că terenul este perfect dreptunghiular. Se cere unghiul format de lovitura jucătorului cu linia de mijloc, astfel ca lovitura să fie cu succes şi pucul să intre în poartă şi să fie cât mai apropiat de stâlpul drept al porţii. Structura unui teren de hockey este prezentată în următoarea figură:
 
p=. !transformari-geometrice?aplicatie-8.1.png 70%!
 
h3. Rezolvare:
 
!> 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.

În desen am colorat cu negru bila iniţială şi cu alb a doua bilă şi imaginile ei. Cu linie punctată am desenat traiectoriile care ar fi atins bila a doua fără a atinge de două ori manta şi cu linie neagră direcţiile pe care manta ar fi atinsă exact de două ori. Observăm că pentru a atinge manta de $N$ ori o bilă trebuie să intre în $N$ alte dreptunghiuri. Deci, asociem poziţiilor dreptunghiurilor un sistem de coordonate în care dreptunghiul iniţial are coordonatele $(0, 0)$. Pentru ca bila să atingă exact $N$ mante, coordonatele $(x, y)$ ale dreptunghiului trebuie să satisfacă egalitatea $|x| + |y| = N$. Mai trebuie să avem grijă ca drumul bilei care atinge $N$ mante să nu atingă a doua bilă înainte de atingerea tuturor mantelor. Aceste observaţii ne duc la următoarea soluţie: pentru toate dreptunghiurile $(x, y)$, care satisfac proprietatea $|x| + |y| < N$, păstrăm într-o structură de date (structura preferată de autor ar fi un 'tabel de dispersie':tabele-hash-prezentare-detaliata) vectorul asociat direcţiei pe care ar fi trebuit lovită prima bilă pentru a ajunge la imaginea celei de a doua bile din acest dreptunghi. Apoi, pentru fiecare dreptunghi pentru care $|x| + |y| = N$, dacă direcţia asociată lui nu este în structura de date, incrementăm numărul de soluţii. Această rezolvare are complexitatea $O(N^2^ log N)$ pentru că normalizarea unei direcţii implică folosirea 'algoritmului lui Euclid':problema/euclid2 ce are complexitate $O(log N)$.