== include(page="template/taskheader" task_id="cmap") ==
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>.
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 între cele mai apropiate două puncte.
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 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. Indicaţii de rezolvare
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.
Î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))$.
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$}).
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ă...
!>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.
# _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 $§$.
*Marius*: 1. Un evaluator ce compară rezultatele cu o eroare de $10^-6^$. 2. Ar mai trebui o sursă în $O(N^2 log(N))$. 3. Sursa ta de $100$ de puncte e în concordanţă cu explicaţia. Eu zic că faci bine în sursă şi că ar merge explicaţia din CLR. 4. Am mai modificat limita de timp la 1s.
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.
Î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.
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") ==
