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.

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.

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

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

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

4579