Parcurgem laturile poligonului intr-o ordine oarecare. Vom avea doi pointeri $cur$ si $next$ care vor reprezenta doua varfuri consecutive de pe poligonul care e solutia curenta. Daca ambele puncte sunt in interiorul semiplanului, atunci solutiei urmatoare ii adaugam punctul urmator. Daca punctul curent e in interior si punctul urmator este in exterior atunci solutiei ii adaugam punctul de intersectie {$p$}. Daca ambele puncte sunt in exterior procesam urmatoarea pereche. Daca punctul curent e in exterior si urmatorul punct este in interior atunci solutiei ii adaugam punctul de intersectie $p$ si punctul urmator. Astfel obtinem un algoritm de complexitate {$O(n^2^)$}. Mentionam ca acest algoritm poate fi folosit si la determinarea intersectiei a doua poligoane convexe.

Articol scris de 'Meditatii Informatica':https://meditatii-informatica.com
 

!preoni-2006/runda-2/solutii?nucleu2.jpg!