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

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.

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