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.

*Marius* 1. Mai multe detalii la implementare 2. Două desene. Primul e greşit. :)
 

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

4579