h2. Indicaţii de rezolvare

În continuare vom descrie un algoritm 'divide şi stăpâneşte':http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm al cărui timp de execuţie este $O(n log{~2~}(n))$.
 
Considerăm $P$ mulţimea tuturor punctelor date. În cazul în care $|P| &le; 3$ se vor considera toate cele <tex> \binom{|P|}{2} </tex> perechi de puncte şi se reţine perechea cea mai apropiată. Dacă $|P| &gt; 3$, se va folosi paradigma divide şi stăpâneşte după cum urmează...
 
# _divide:_ determină o dreaptă verticală $d$ care împarte mulţimea $P$, menţionată mai sus, în două submulţimi $P{~s~}$ şi $P{~d~}$, astfel încât $||P{~s~}| - |P{~d~}|| &le; 1$, adică numărul punctelor din cele două mulţimi diferă cu cel mult unu. Punctele din $P{~s~}$ se găsesc în stânga dreptei verticale $d$ iar cele din $P{~d~}$ în dreapta.
# _stăpâneşte:_ se fac două apeluri recursive, unul pentru a determina cea mai apropiată pereche de puncte din $P{~s~}$, şi celălalt pentru a determina cea mai apropiată pereche de puncte din $P{~d~}$. Fie $&sect;{~s~}$ şi $&sect;{~d~}$ valorile returnate şi fie $&sect; = min(&sect;{~s~}, &sect;{~d~})$.
# _combină:_ cea mai apropiată pereche este cea cu distanţa $&sect;$, determinată de unul din apelurile recursive, sau este o pereche de puncte cu un punct în $P{~s~}$ şi celălalt în $P{~d~}$. Observaţi că, dacă există o pereche de puncte cu distanţa mai mică decât $&sect;$, atunci ambele puncte ale perechii trebuie să fie, faţă de dreapta $d$, la distanţa maximă $&sect;$. Astfel, conform desenului alăturat, ambele trebuie să se situeze într-o regiune de lăţime $2&sect;$, centrată în jurul dreptei verticale $d$. Pentru a găsi o astfel de pereche, dacă există, algoritmul urmează paşii...
** contruieşte un şir $Y$ care conţine toate punctele ce sunt la o distanţă cel mult $&sect;$ faţă de dreapta verticală $d$. Şirul este sortat după ordonată.
** pentru fiecare punct $p$ din $Y$, algoritmul încearcă să găsească punctele din $Y$ care sunt la o distanţă de cel mult $&sect;$ unităţi faţă de $p$. Aşa cum vom arăta mai jos, este necesar să fie considerate doar $7$ puncte din $Y$, care urmează după $p$. Algoritmul calculează distanţa de la $p$ la fiecare dintre cele $7$ puncte şi reţine distanţa $&sect;'$ a perechii celei mai apropiate, găsite dintre toate perechile de puncte din $Y$.
** dacă $&sect;' &lt; &sect;$, atunci regiunea verficală conţine, într-adevăr, o pereche mai apropiată decât cea care a fost găsită prin apelurile recursive. Se returnează astfel distanţa $&sect;'$. Altfel, este returnată distanţa $&sect;$.
 
_Corectitudinea_

Un algoritm ce consideră fiecare pereche de puncte din cele <tex> \binom{n}{2} </tex> are complexitatea $O(n^2^)$ şi obţine '$20$ de puncte':job_detail/378896?action=view-source.

În primul rând, recursivitatea se opreşte când $|P| ≤ 3$ pentru a evita să împărţim vreodată o mulţime cu un singur punct.

În continuare vom descrie un algoritm 'divide şi stăpâneşte':http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm al cărui timp de execuţie este $O(n log{~2~}(n))$.

În al doilea rând, să demonstrăm proprietatea conform căreia avem nevoie doar de $7$ puncte care urmează după fiecare punct $p$ din şirul $Y$. Presupunem că la un anumit nivel al recursivităţii, cea mai apropiată pereche de puncte este $p{~s~}$ din $P{~s~}$ şi $p{~d~}$ din $P{~d~}$. Astfel, distanţa $§'$ dintre $p{~s~}$ şi $p{~d~}$ este strict mai mică decât $§$. Punctul $p{~s~}$ trebuie să fie pe dreapta $d$ sau în stânga ei şi la o distanţă mai mică de $§$ unităţi. În mod analog, $p{~d~}$ este pe sau în dreapta dreptei $d$ la o distanţă mai mică de $§$ unităţi. Mai mult, $p{~s~}$ şi $p{~d~}$ se află pe verticală la o distanţă de cel mult $§$ unităţi unul faţă de celălalt. Deci, aşa cum se arată în figura alăturată, cele două puncte se află într-un dreptunghi $§ x 2§$ centrat pe dreapta $d$.

Considerăm $P$ mulţimea tuturor punctelor date. În cazul în care $|P| &lt; 3$ se vor considera toate cele <tex> \binom{|P|}{2} </tex> perechi de puncte şi se reţine perechea cea mai apropiată. Dacă $|P| &ge; 3$, se va folosi paradigma divide şi stăpâneşte după cum urmează...

Arătăm în continuare că cel mult $8$ puncte din $P$ se pot găsi în interiorul acestui dreptunghi $§ x 2§$. Studiem pătratul $§ x §$ care reprezintă jumătatea stângă a dreptunghiului. Deoarece toate punctele din $P{~s~}$ sunt la o distanţă de cel puţin $§$ unităţi, cel mult $4$ puncte se pot situa în interiorul acestui pătrat. În mod analog, cel mult $4$ puncte din $P{~d~}$ se pot situa în interiorul pătratului $§ x §$ ce reprezintă jumătatea dreaptă a dreptunghiului. Deci, cel mult $8$ puncte din $P$ se pot situa în interiorul dreptunghiului $§ x 2§$.

# _Divide:_ Determină o dreaptă verticală $§$ care împarte mulţimea $P$, menţionată mai sus, în două submulţimi $P{~s~}$ şi $P{~d~}$, astfel încât $||P{~s~}| - |P{~d~}|| ≤ 1$, adică numărul punctelor din cele două mulţimi diferă cu cel mult unu.
# _Stăpâneşte:_ Se fac două apeluri recursive, unul pentru a determina cea mai apropiată pereche de puncte din $P{~s~}$, şi celălalt pentru a determina cea mai apropiată pereche de puncte din $P{~d~}$. Fie $d{~s~}$ şi $d{~d~}$ valorile returnate şi fie $d = min(d{~s~}, d{~d~})$.
# _Combină:_ Cea mai apropiată pereche este cea cu distanţa $d$, determinată de unul din apelurile recursive, sau este o pereche de puncte cu un punct în $P{~s~}$ şi celălalt în $P{~d~}$. Observaţi că, dacă există o pereche de puncte cu distanţa mai mică decât $d$, atunci ambele puncte ale perechii trebuie să fie, daţă de dreapta $§$, la distanţa maximă $d$. Astfel, conform desenului alăturat, ambele trebuie să se situeze într-o regiune de lăţime $2d$, centrată în jurul dreptei verticale $§$. Pentru a găsi o astfel de pereche, dacă există, algoritmul urmează paşii...
** Contruieşte un şir $Y$ care conţine toate punctele ce sunt la o distanţă cel mult $d$ faţă de dreapta verticală $§$. Şirul este sortat după ordonată.
** Pentru fiecare punct $p$ din $Y$, algoritmul încearcă să găsească punctele din $Y$ care sunt la o distanţă de cel mult $d$ unităţi faţă de $p$. Aşa cum vom arăta mai jos, este necesar să fie considerate doar $7$ puncte din $Y$, care urmează după $p$. Algoritmul calculează distanţa de la $p$ la fiecare dintre cele $7$ puncte şi reţine distanţa $d'$ a parechii celei mai apropiate, găsite dintre toate perechile de puncte din $Y$.
** Dacă $d' < d$, atunci regiunea verficală conţine, într-adevăr, o pereche mai apropiată decât cea care a fost găsită prin apelurile recursive. Se returnează astfel distanţa $d'$. Altfel, este returnată distanţa $d$.

Atunci, presupunând că $p{~s~}$ apare cât de devreme este posibil în şirul $Y$, şi $p{~d~}$ cât mai târziu posibil, $p{~d~}$ este într-una din cele $7$ poziţii care urmează după $p{~s~}$. Deci, am demonstrat corectitudinea algoritmului pentru determinarea perechii celei mai apropiate.
h3. Soluţii

O alta soluţie de complexitate $O(N*N*log{~2~}N)$ sortează numerele crescător după abscisa şi apoi foloseşte un algoritm $divide et impera$. Se împart cele $N$ puncte în doua grupuri $st$ şi $dr$, se calculează $st_min$ şi $dr_min$, distanta intre cele mai apropiate puncte din grupul $st$ şi $dr$, apoi se calculează $st_dr_min$, distanta intre cele mai apropiate 2 puncte, unul aparţinând grupului $st$ şi altul lui $dr$. Distanta intre cele mai apropiate puncte o sa fie minim({$st_min$}, {$dr_min$}, {$st_dr_min$}).

Un algoritm ce consideră fiecare pereche de puncte din cele <tex> \binom{n}{2} </tex> are complexitatea $O(n^2^)$ şi obţine '$20$ de puncte':job_detail/378896?action=view-source.

!>problema/cmap?Closest_pair.jpg 50%!
Se observa ca cea mai costisitoare operaţie este cea la care se calculează $st_dr_min$. Aceasta se poate reduce de la $O(N*N)$ la $O(N)$ folosind următoarea observaţie: notam cu $dist$ minimul dintre $st_min$ si $dr_min$. Pentru orice punct $P$ din grupul $st$ este suficient sa ne uitam la punctele din dreptunghiul cu laturile $dist$ si $2*dist$ din grupul $dr$ ca in figura.
Se observa ca în dreptunghi sunt maxim 6 astfel de puncte, deci complexitatea se reduce de la $O(N*N)$ la $O(6*N)$, astfel complexitatea finala devenind $O(N*log{~2~}N)$. Aceasta 'soluţie':job_detail/378894?action=view-source foloseşte ideea prezentata mai sus şi obţine 100 de puncte.

Depinzând de implementare, există soluţie de complexitate $O(n log{~2~}^2^(n))$ şi soluţie de complexitate $O(n log{~2~}(n))$. Soluţia din urmă presupune ca la revenirea din apelul recursiv, cele două submulţimi de puncte sortate după ordonată să fie interclasate în timp liniar şi nu sortate.

*Marius*: 1. Un evaluator ce compară rezultatele cu o eroare de $10^-6^$. 2. Ar mai trebui o sursă în $O(N^2 log(N))$. 3. Sursa ta de $100$ de puncte nu e în concordanţă cu explicaţia. Eu zic că faci bine în sursă şi că ar merge explicaţia din CLR. 4. Am mai modificat limita de timp la 1s.

h2. Aplicaţii