*devilkind* uitativa putin la solutia asta ptr ca nu sunt foarte sigur pe complexitati - in special cand e vb de poligoane concave. Mie mi se pare ca aia e complexitatea insa e posibil sa ma insel
*cotizo* da e corect - asta e si rezolvarea problemei "poligon"

h3. {+Cele mai departate doua puncte+}
 
Enunt: Se da o multime de $N$ puncte in plan. Sa se determine perechea de puncte pentru care distanta dintre cele doua este maxima.
 
O prima solutie ar fi calcularea distantei intre fiecare pereche de $2$ puncte si pastrarea ca solutie a perechei cu distanta maxima. Desigur, aceasta solutie are complexitate {$O(N^2^)$} si nu este eficienta.
 
O rezolvare mai eficienta porneste de la observatia ca perechea cautata se afla in mod evident pe infasuratoarea convexa a punctelor. Vom incepe prin a fixa un punct oarecare pe infasuratoare si vom parcurge restul punctelor de pe infasuratoare in oricare sens (trigonometric sau orar). Distanta intre punctul fixat si punctul la care am ajuns in parcugere va creste pana la un moment dat si apoi va incepe sa scada. Retinem punctul aflat la distanta maxima fata de cel fixat. Vom avea acum perechea de puncte $X$ (punctul fixat initial), $Y$ (cel mai departat punct de acesta) care este o posibila solutie.
 
Apoi vom pleca de la $X$ si vom continua sa parcurgem restul punctelor de pe infasuratoare in sensul ales initial. Pentru fiecare punct din aceasta parcurgere, vom incerca sa gasim punctul de pe infasuratoare pentru care se obtine o distanta maxima. Daca am reface algoritmul folosit pentru $X$ am obtine o complexitate de {$O(N^2^)$} ceea ce este ineficient. Ca sa reducem complexitatea, notam punctul la care am ajuns in parcurgere cu $A$, si observam ca pentru oricare punct dintre $A$ si $Y$ in sensul ales, distanta intre acesta si $A$ va fi mai mica decat distanta dintre $X$ si $Y$, asadar nu poate fi o solutie. Astfel, pentru fiecare punct $A$, parcurgem punctele incepand cu punctul $Y$ in sensul ales pana cand distanta dintre $A$ si punctul la care am ajuns va incepe sa scada. Pastram distanta maxima, verificam daca este mai buna decat solutia obtinuta pana acum si apoi trecem la urmatorul punct $A$.
 
Complexitatea acestei solutii este de {$O(N*log N)$} pentru infasuratoare si {$O(N)$} pentru aflarea celor mai departate 2 puncte asadar {$O(N*log N)$}.
 
 

h1. TODO
*Feedback (Stefan):* Articolul trebuie imbracat intr-o forma mai prezentabila. Nu trebuie sa ramana doar o lista de formule si schelete de probleme. De asemenea, trebuie compactat si eliminate spatiile mari care il fac greu de citit.