== 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. Distanţa euclidiană dintre două puncte <tex> A(x_{1}, y_{1}) </tex> şi <tex>B (x_{2}, y_{2}) </tex> se calculează conform formulei: <tex> \sqrt{(x_{1} - x_{2})^2 + (y_{1} - y_{2})^2} </tex>.
h3. Cerinţă
Să se determine distanţa dintre 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 punctelor.
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$
* $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 $2 ≤ 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.
Î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$ o submulţime a punctelor date. Iniţial, $P$ va conţine toate punctele. În cazul în care $|P| ≤ 3$ se vor considera toate cele <tex> \binom{|P|}{2} </tex> perechi de puncte şi se reţine perechea cea mai apropiată. Dacă $|P| > 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~})$.
# _combină:_ cea mai apropiată pereche este cea cu distanţa $§$, 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 $§$, atunci ambele puncte ale perechii trebuie să fie, faţă de dreapta $d$, la distanţa maximă $§$. Astfel, conform desenului alăturat, ambele trebuie să se situeze într-o regiune de lăţime $2§$, centrată în jurul dreptei verticale $d$. 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 $§$ faţă de dreapta verticală $d$. Ş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 $§$ 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.
În al doilea rând, să demonstrăm proprietatea conform căreia avem nevoie doar de $7$ puncte care urmează după fiecare punct $p$ din şirul $Y$. Presupunem că la un anumit nivel al recursivităţii, cea mai apropiată pereche de puncte este $p{~s~}$ din $P{~s~}$ şi $p{~d~}$ din $P{~d~}$. Astfel, distanţa $§'$ dintre $p{~s~}$ şi $p{~d~}$ este strict mai mică decât $§$. Punctul $p{~s~}$ trebuie să fie pe dreapta $d$ sau în stânga ei şi la o distanţă mai mică de $§$ unităţi. În mod analog, $p{~d~}$ este pe sau în dreapta dreptei $d$ la o distanţă mai mică de $§$ unităţi. Mai mult, $p{~s~}$ şi $p{~d~}$ se află pe verticală la o distanţă de cel mult $§$ unităţi unul faţă de celălalt. Deci, aşa cum se arată în figura alăturată, cele două puncte se află într-un dreptunghi $§ x 2§$ centrat pe dreapta $d$.
Arătăm în continuare că cel mult $8$ puncte din $P$ se pot găsi în interiorul acestui dreptunghi $§ x 2§$. Studiem pătratul $§ x §$ care reprezintă jumătatea stângă a dreptunghiului. Deoarece toate punctele din $P{~s~}$ sunt la o distanţă de cel puţin $§$ unităţi, cel mult $4$ puncte se pot situa în interiorul acestui pătrat. În mod analog, cel mult $4$ puncte din $P{~d~}$ se pot situa în interiorul pătratului $§ x §$ ce reprezintă jumătatea dreaptă a dreptunghiului. Deci, cel mult $8$ puncte din $P$ se pot situa în interiorul dreptunghiului $§ x 2§$.
Atunci, presupunând că $p{~s~}$ apare cât de devreme este posibil în şirul $Y$, şi $p{~d~}$ cât mai târziu posibil, $p{~d~}$ este într-una din cele $7$ poziţii care urmează după $p{~s~}$. Deci, am demonstrat corectitudinea algoritmului pentru determinarea perechii celei mai apropiate.
h3. Soluţii
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.
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$}).
Î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.
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 in dreptunghi sunt maxim 6 astfel de puncte, deci complexitatea se reduce de la $O(N*N)$ la $O(6*N)$.
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
# 'Harta2':problema/harta2
# 'Min Perimeter':http://code.google.com/codejam/contest/dashboard?c=311101
== include(page="template/taskfooter" task_id="cmap") ==
