На плоскости взяли несколько точек, причём никакие три из них не лежат на одной прямой. Когда через каждую пару точек

можно провести прямую, тогда это называется выпуклая оболочка. Она представляет собой минимальное выпуклое множество, содержащее все заданные точки.

Для построения выпуклой оболочки есть несколько алгоритмов. Один из самых популярных алгоритмов - алгоритм Грэхэма.

Алгоритм Грэхэма состоит из следующих шагов:

1. Найти самую нижнюю левую точку и поместить ее в начало списка точек.
2. Отсортировать остальные точки по углу, который они образуют с горизонтальной осью, начиная от самой левой точки. Если несколько точек имеют одинаковый угол, выбрать ту, которая находится ближе к начальной точке.
3. Создать пустой стек, поместить начальную точку и две следующих после нее точки в стек.
4. Проходить по остальным точкам, начиная с четвертой, и для каждой точки проверять, образует ли она с последними двуми точками в стеке правый поворот. Если да, убирать последнюю точку из стека и повторять проверку до тех пор, пока ситуация не изменится.
5. Добавить текущую точку в стек.
6. После прохода по всем точкам, в стеке останутся только точки, которые образуют выпуклую оболочку.