== include(page="template/taskheader" task_id="cmap") ==

Se dau $N$ puncte în plan cu coordonate numere întregi. Sa se determine distanta intre cele mai apropiate 2 puncte.

Considerăm un plan euclidian ce conţine $n$ puncte date prin coordonatele lor. În acest plan, dacă <tex> p(p_{1}, p_{2}) </tex> iar <tex> q(q_{1}, q_{2}) </tex>, atunci distanţa dintre aceste două puncte este: <tex> \sqrt{(p_{1} - q_{1})^2 + (p_{2} - q_{2})^2} </tex>.
 
h3. Cerinţă
 
Să se determine distanţa între cele mai apropiate două puncte.

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 doua numere $X{~i~}$ şi $Y{~i~}$, 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 celui de al i-lea punct.

h2. Date de ieşire

În fişierul de ieşire $cmap.out$ se va afişa distanta intre cele mai apropiate 2 puncte.

În fişierul de ieşire $cmap.out$ se va afişa distanţa dintre cele mai apropiate două puncte din planul euclidian.

h2. Restricţii

* $1 ≤ N ≤ 100 000$
* $-1 000 000 000 ≤ X{~i~} ≤ 1 000 000 000$
* $-1 000 000 000 ≤ Y{~i~} ≤ 1 000 000 000$
* Oricare doua puncte sunt distincte.
* Pentru $20%$ din teste $1 ≤ N ≤ 1 000$

* $1 ≤ 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.
* Pentru $20%$ din teste $1 ≤ n ≤ 1 000$.

h2. Exemplu

h2. Indicaţii de rezolvare

O 'soluţie':job_detail/378896?action=view-source brute-force de complexitate $O(N*N)$ obţine 20 de puncte.

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.

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