h2. Date de intrare

Fişierul de intrare $cmap.in$ conţine pe prima linie un număr $n$ cu semnificaţia din enunţ. Pe următoarele $n$ linii se vor afla câte două numere $x{~i~}$ şi $y{~i~}$, separate printr-un spaţiu, semnificând coordonatele celui de al i-lea punct.

Fişierul de intrare $cmap.in$ conţine pe prima linie un număr $n$ cu semnificaţia din enunţ. Pe următoarele $n$ linii se vor afla câte două numere $x{~i~}$ şi $y{~i~}$, separate printr-un spaţiu, semnificând coordonatele punctelor.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ n ≤ 100 000$.

* $2 ≤ n ≤ 100 000$.

* $-10^9^ ≤ x{~i~} ≤ 10^9^$.
* $-10^9^ ≤ y{~i~} ≤ 10^9^$.
* Oricare două puncte sunt distincte.
* Orice număr se găseşte la coordonate numere întregi.
* Răspunsul va fi considerat corect dacă are o eroare de cel mult $10^-6^$.

* Pentru $20%$ din teste $1 ≤ n ≤ 1 000$.

* Pentru $20%$ din teste $2 ≤ n ≤ 1 000$.

h2. Exemplu

Î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ă...

Considerăm $P$ o submulţime a punctelor date. Iniţial, $P$ va conţine toate punctele. Î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~}|| ≤ 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 $§{~s~}$ şi $§{~d~}$ valorile returnate şi fie $§ = min(§{~s~}, §{~d~})$.

** pentru fiecare punct $p$ din $Y$, algoritmul încearcă să găsească punctele din $Y$ care sunt la o distanţă de cel mult $§$ 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 $§'$ a perechii celei mai apropiate, găsite dintre toate perechile de puncte din $Y$.
** dacă $§' < §$, 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 $§'$. Altfel, este returnată distanţa $§$.

p=. !problema/cmap?cmap-1.png 40%! !problema/cmap?cmap-3.png 40%!
 

_Corectitudinea_
Î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.

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.

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.

În implementare, se va porni de la un şir sortat după abscisă iar în caz de egalitate după ordonată. Şirul se va împărţi în două submulţimi, se va rezolva recursiv fiecare submulţime, iar la revenirea din recursivitate se va obţine şirul $Y$ interclasând cele două subşiruri sortate după ordonată din cele două apeluri recursive. După care se va fixa câte un punct $p$ din $Y$ şi se vor analiza următoarele $7$ puncte.

*Marius* 1. Mai multe detalii la implementare 2. Două desene 3. Schimbate teste pentru ca sursa în log^2^ să ia 70 şi nu doar 40.

Depinzând de implementare, există soluţie de complexitate '$O(n log{~2~}^2^(n))$':job_detail/387350?action=view-source şi soluţie de complexitate '$O(n log{~2~}(n))$':job_detail/383250?action=view-source. 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.

h2. Aplicaţii

4579