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, 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.
 
h3. Rezolvare:
 
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ă.
 
!> transformari-geometrice?aplicatie-7.1.png 80%!
 
Î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, dacă poziţiilor dreptunghiurilor le ar fi asociat un sistem de coordonate în care dreptunghiul iniţial are coordonatele $(0, 0)$. Am văzut că o soluţie este asociată cu un dreptunghi, 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, deşi 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) 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 ce are complexitate $O(log N)$.