Acum trebuie doar sa calculam cel mai mic cerc care contine punctele din setul I in interior si care are punctul {$P$} pe circumferinta. Vom extinde {$C{~I~}$} adaugand un nou parametru. Astfel notam cu {$C{~I,B~}$} cercul de raza minima ce contine setul {$I$} de puncte in interior si punctele din setul {$B$} pe circumferinta (pot exista si alte puncte pe circumferinta, dar cele din setul {$B$} sunt fortate). Cercul de raza minima care contine toate punctele va fi {$C{~S,{}~}$}.

Calcularea lui {$C{~I,B~}$} se face in mod recursiv. Daca {$B$} are cel putin 3 puncte atunci {$C{~I,B~}$} devine cercul determinat de acestea. In caz contrar se alege un punct random (notat cu {$P$}) din setul {$I$}. In cazul in care punctul {$P$} se afla in interiorul cercului {$C{~I-{P},B~}$}, atunci cercul acesta nu mai trebuie marit si {$C{~I,B~}$} devine egal cu {$C{~I-{P},B~}$}. In cazul in care punctul {$P$} nu se afla in interiorul acelui cerc {$C{~I,B~}$} devine egal cu {$C{~I-{P},B ∪ {P}~}$}.

Calcularea lui {$C{~I,B~}$} se va face in mod recursiv. Mai jos voi prezenta un pseudocod pentru functia respectiva:

Singura neclaritate care ramane este _de ce_ complexitatea este {$O(N)$}. Datorita alegerii punctelor in mod random in timpul calcularii lui {$C{~I,B~}$}, fiecare punct din {$I$} are probabilitatea {$^1^/{~|I|~}$} de a fi ales. Pe masura ce calculam {$C{~I,B~}$}, pastrand acelasi {$B$}, pot exista doar 3 puncte {$P$} pentru care este nevoie sa calculam {$C{~I,B ∪ {P}~}$}.

==code(c) |
Cerc MINCIRCLE( Set I, Set B )
    Daca |I| == 0 sau |B| >= 3
        returneaza cercul format de punctele din B
    P = punct random apartinand setului I
    C = MINCIRCLE( I - {P}, B )
    Daca P nu este inclus in C
        returneaza MINCIRCLE( I - {P}, B + {P} )
    returneaza C
==

TODO explicatie complexitate scrisa ceva mai bine, poza

Singurul lucru care mai ramane de demonstrat este _de ce_ complexitatea este {$O(N)$}.
 
Pentru {$|B|$} egal cu 3, determinarea cercului este triviala si are complexitatea {$O(1)$}.
 
Pentru {$|B|$} egal cu 2, complexitatea este evident {$O(N)$}, deoarece calcularea cercului de raza minima pentru setul {$B + {P}$} se rezolva in {$O(1)$}.
 
Pentru {$|B|$} egal cu 1, notam cu {$T(N)$} numarul de operatii folosite pentru a calcula {$C{~S,B~}$}, unde {$|S|$} este egal cu {$N$}. Atunci {$T(N)$} respecta relatia:
 
* {$T(N) <= T(N - 1) + Probabilitate( P nu apartine C{~I - {P},B~} ) * O(N)$} + O(1)
Primul termen din partea dreapta a inegalitatii reflecta numarul de operatii folosite de apelul recursiv MINCIRCLE{$(I - {P}, B)$}, iar al doilea termen reflecta numarul de operatii folosite pentru cazurile in care {$P$} nu apartine cercului {$C$}.
 
Datorita alegerii punctelor in mod random in timpul calcularii lui {$C{~I,B~}$}, fiecare punct din {$I$} are probabilitatea {$^1^/{~N~}$} de a fi ales. Datorita faptului ca exista cel mult 3 puncte care se vor afla in exteriorul cercului {$C{~I - {P},B~}$} pentru orice set I de puncte, probabilitatea ca {$P$} sa nu apartina cercului {$C{~I - {P},B~}$} este egala cu {$^3^/{~N~}$}. Astfel inegalitatea de mai sus devine:
 
* {$T(N) <= T(N - 1) + ^3^/{~N~}*O(N) + O(1)$}
ceea ce este echivalent cu
* {$T(N) <= T(N - 1) + O(1)$}
 
Astfel complexitatea devine {$O(N)$}. Se demonstreaza analog pentru {$|B|$} egal cu 0.
 
 
%{color:red}TODO: demonstrat de ce pentru orice set de puncte exista doar 3 care pot sa fie in afara cercului%

Exercitii: "SPOJ ALIENS":http://www.spoj.pl/problems/ALIENS/