h3. (problema grea, clasa a 10-a)

Este evident ca cele doua poligoane convexe pot fi separate de o dreapta care sa treaca printr-un varf $A$ de pe primul poligon si un varf $B$ de pe cel de-al doilea. Astfel, dreapta imparte planul in doua semiplane si in fiecare din cele doua semiplane se afla cate un poligon convex.
Dintre cele $N$ puncte alegem toate perechile de puncte {$(X Y)$} si presupunem ca dreapta determinata de aceste doua puncte separa cele doua poligoane, iar punctul $X$ este varf pentru primul poligon si punctul $Y$ pentru cel de-al doilea. Pentru o dreapta fixata, putem aplica pentru fiecare din cele semiplane un algoritm de infasuratoare convexa ( verificand apoi daca infasuratoarea convexa contine toate punctele din semiplanul respectiv ) in {$O(N log N)$}, rezultand o complexitate totala de {$O(N^3^ log N)$}. Pentru a obtine complexitatea {$O(N^3^)$}, putem sorta punctele in functie de ordonata si apoi in functie de abscisa de la inceput. Astfel, in algoritmul Graham pentru poligoane convexe nu mai este necesara resortarea punctelor si algoritmul, pentru o dreapta fixata, dureaza {$O(h1) + O(h2)$}, unde h1 si h2 sunt numarul de puncte din cele doua semiplane. Cum {$O(h1 + h2)$} = {$O(N)$}, complexitatea algoritmului este O(N^3).
 
 

h2. 'P-Sir':problema/psir
h3. (problema usoara, clasele 11-12)