h3. Algoritm de complexitate $O(log N)$ - varianta 1

Folosind relatiile de recurenta de mai sus, putem construi o matrice $A$ de iteratie si vom privi $T[i]$ ca pe un vector coloana. Avem relatia: $T[i] = A * T[i-1]$. $T[N] = A^N-1^ * T[1]$. $T[1]$ este cunoscut direct, iar $A^N-1^$ se poate calcula in complexitate $O(log N)$, folosind exponentiere logaritmica.

Folosind relatiile de recurenta de mai sus, putem construi o matrice $A$ de iteratie si vom privi $T[i]$ ca pe un vector coloana. Avem relatia: $T[i] = A * T[i-1]$. $T[N] = A^N-1^ * T[ 1 ]$. $T[ 1 ]$ este cunoscut direct, iar $A^N-1^$ se poate calcula in complexitate $O(log N)$, folosind exponentiere logaritmica.

h3. Algoritm de complexitate $O(log N)$ - varianta 2

Aceste formule (sau altele echivalente) pot fi obtinute folosind urmatorul rationament: furnica se poate afla in orice pozitie aflata la o distanta care are aceeasi paritate ca si $t$, fata de pozitia initiala. Pentru pozitia de start $'C'$, aceste pozitii formeaza niste "romburi", iar pentru pozitia de start $'S'$, aceste pozitii formeaza niste diagonale "secundare".

h2. 'Flori2':problema.flori2

h2. 'Flori2':problema/flori2

Pentru fiecare punct $i$, se sorteaza toate celelalte $N-1$ puncte in jurul punctului $i$ (in functie de unghi). Parcurgand apoi punctele in ordinea sortata, vom determina numarul maxim de puncte avand acelasi unghi fata de $i$ (folosind o precizie corespunzatoare, de $10^-8^$, de exemplu). Fie acest numar $MAX{~i~}$. Raspunsul cautat este $maxim{MAX{~i~} + 1}$ si se obtine in complexitate $O(N^2^*logN)$.

O metoda simpla este sa translatam primul cerc in originea sistemului de axe de coordonate si sa il rotim pe cel de-al doilea pana cand centrul acestuia se afla pe axa $OX$ (la coordonata $X$ egala cu distanta dintre cele $2$ centre). Trebuie analizate cateva cazuri, pe baza valorilor razelor celor $2$ cercuri si a distantei dintre centrele lor (cazurile simple sunt cand unul din cercuri se afla complet in interiorul, respectiv complet in exteriorul celuilalt cerc). In cazul in care se decide ca cele $2$ cercuri se intersecteaza in $2$ puncte, vom observa ca, in urma translatiei si rotatiei efectuate, cele $2$ puncte de intersectie se vor afla la aceeasi coordonata $x$, dar la coordonate $y$ opuse (egale in modul, dar opuse ca semn). Vom determina cele $2$ coordonate folosind 'Teorema lui Pitagora generalizata':http://en.wikipedia.org/wiki/Pythagorean_theorem in triunghiul format din centrele celor $2$ cercuri si fiecare din cele $2$ puncte de intersectie (deoarece cunoastem lungimile tuturor laturilor). Aria comuna a celor 2 cercuri este acum formata din 2 bucati de cerc, de o parte si de alta a segmentului ce uneste cele 2 puncte de intersectie. Aria fiecareia din cele 2 bucati de cerc se poate scrie ca diferenta dintre aria unui sector de cerc (corespunzator segmentului ce uneste punctele de intersectie) si aria unui triunghi (format din centrul unui cerc si cele 2 puncte de intersectie). O formulare suficient de generala a expresiilor ce calculeaza aria comuna permite tratarea unitara a cazurilor in care cel de-al doilea cerc are centrul in exteriorul, respectiv in interiorul primului cerc.

h3. Link-uri utile:

h3. Link-uri utile
 

* 'Circle-Cirlce Intersection / Mathworld':http://mathworld.wolfram.com/Circle-CircleIntersection.html

h3. Probleme asemanatoare:

h3. Probleme asemanatoare
 

* 'Cercuri / Happy Coding 2005 [2]':problema/cercuri
* 'Cerc2 / Happy Coding 2007':problema/cerc2

Observam ca distanta dintre oricare $2$ puncte in care fotonul atinge cercul este aceeasi ca cea dintre punctul initial si punctul $(R*cos(alfa), R*sin(alfa))$. Fie aceasta distanta $D$. Dupa $S$ secunde, fotonul se afla la o distanta $S mod D$ de ultimul punct in care a atins cercul. Operatia $modulo$ se poate defini si pentru numere reale, scriind $S$ ca fiind $k*D + r$, unde k este un numar intreg (si $r$ este restul impartirii). Putem folosi acum Teorema lui Pitagora generalizata, pentru a determina distanta de la foton la centrul cercului, in triunghiul format din punctul curent, ultimul punct de atingere a cercului si centrul cercului. O metoda mai simpla de a calcula aceasta distanta este de a calcula distanta de la centrul cercului la segmentul dintre $2$ puncte consecutive in care fotonul atinge cercul (aceasta distanta este {$R*sin(beta)$}). Cum perpendiculara din centrul cercului pe acest segment il intersecteaza exact in mijloc, putem folosi distanta fotonului fata de mijlocul segmentului si apoi Teorema lui Pitagora intr-un triunghi dreptunghic, pentru a calcula distanta de la foton la centrul cercului (in triunghiul format de centrul cercului, mijlocul segmentului si pozitia fotonului, distanta respectiva este lungimea ipotenuzei).

h3. Probleme asemanatoare:

h3. Probleme asemanatoare

* 'Cercuri / Happy Coding 2005 [2]':problema/cercuri
* 'Cercuri3 / Happy Coding 2007':problema/cercuri3