h2. Indicaţii de rezolvare

O soluţie ce consideră fiecare pereche de puncte are complexitatea $O(N^2^)$ şi obţine '$20$ de puncte':job_detail/378896?action=view-source.

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 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| &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ă...
 
# _Divide:_ Determină o dreaptă verticală $&sect;$ 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.
# _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 $&sect;$, 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 $&sect;$. 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ă $&sect;$. Ş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' &lt; 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$.
 

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