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