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

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. !>problema/pinex?Closest_pair.jpg 50%!
Se observa ca in dreptunghi sunt maxim 6 astfel de puncte, deci complexitatea se reduce de la $O(N*N)$ la $O(6*N)$.

!>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.

h2. Aplicaţii