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.
Индекс
Элементарные функции    Линейные уравнения    Нелинейные уравнения    Случайные числа


Hosted by uCoz