Pentru fiecare punct {$P$}, putem determina in timp constant daca punctul se afla in interiorului cercului {$C{~I~}$}. In cazul in care {$P$} este inclus in {$C{~I~}$}, atunci {$C{~I+{P}~}$} va fi egal cu {$C{~I~}$}. In caz contrar, trebuie sa schimbam cercul {$C{~I~}$} pentru a cuprinde si acest punct. Cercul ce cuprinde toate punctele va fi evident {$C{~S~}$}, unde {$S$} este setul de puncte dat. Singura problema este cum determinam acel cerc modificat.

!>minimum-enclosing-circle?punctlasatinext.png 63%! La o prima vedere se pare ca trebuie doar sa calculam cel mai mic cerc ce include {$P$} alaturi de cele 3 puncte ce determinau {$C{~I~}$} fara sa mai luam in considerare celelalte puncte din set, insa nu este greu de gasit un caz pentru care raman puncte in exterior, asa cum se vede in poza alaturata.

!>minimum-enclosing-circle?punctlasatinext.png 62%! La o prima vedere se pare ca trebuie doar sa calculam cel mai mic cerc ce include {$P$} alaturi de cele 3 puncte ce determinau {$C{~I~}$} fara sa mai luam in considerare celelalte puncte din set, insa nu este greu de gasit un caz pentru care raman puncte in exterior, asa cum se vede in poza alaturata.

Vom demonstra in continuare ca daca punctul {$P$} se afla in exteriorul cercului {$C{~I~}$}, atunci el trebuie sa fie pe circumferinta cercului {$C{~I+{P}~}$}.

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}~}$}.

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 {$D{~I,B+{P}}$}.

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 {$D{~I,B+{P}}$}.
 
TODO explicatie complexitate scrisa ceva mai bine, poza

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