# Not f do begin

Not f do begin if СЛЕД[v]=w then f:=true; if&lt;три точки v, СЛЕД[v], СЛЕД[СЛЕД[v]] образуют «левый поворот»&gt; then v:=СЛЕД[v] else begin УДАЛИТЬ СЛЕД[v]; v:=ПРЕД[v]; end; end; end; Второй метод. Утверждение. Отрезок L, определяемый двумя точками, является ребром выпуклой оболочки тогда и только тогда, когда все другие точки множества S лежат на L или с одной стороны от него. Из этого утверждения «вытекает» следующая логика. N точек определяют порядка О(N2) отрезков. Для каждого из этих отрезков за линейное время можно определить положение остальных N-2 точек относительно него. Таким образом, за время, пропорциональное О(N3), можно найти все пары точек, определяющих ребра выпуклой оболочки. Затем эти точки следует расположить в порядке последовательных вершин оболочки. Джарвис заметил, что данную идею можно улучшить, если учесть следующий факт. Если установлено, что отрезок q1q2 является ребром оболочки, то должно существовать другое ребро с концом в точке q2.

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа