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 70%!

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

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

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