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

*Paul:* Nu sunt consitente notatiile. Cand apare (p1, p2), (q1, q2), cand apare (x, y). Cred ca notatia cu (x, y) e mai naturala.
 

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ţă

* $-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$.
h2. Exemplu

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.

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

h2. Aplicaţii
# 'Harta2':problema/harta2