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

** 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

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