Этот алгоритм за O( n ) времени 'выправляет' впуклости многоугольника, то есть замкнутой непересекающейся ломаной, строя таким образом выпуклую оболочку. Что интересно, точки могут поступать по мере выполнения алгоритма, и их количество может быть заранее не известно. Главное, чтобы ломаная не пересекалась. Для начала объявим вспомогательную функцию, которая для любой тройки x, y, z будет f>0, f=0 или f<0 в зависимости от того, находится ли z справа, на одной линии или слева от линии (x, y). Пусть ломаная задана точками v1, ..., vm. Алгоритм начинает с пустого дека D. Дек - список с операциями: push v - положить элемент на верх дека, insert v - положить элемент под низ дека, pop - убрать верхний элемент дека, remove - удалить нижний элемент дека. Псевдокод. Шаг 1: Ввод v1, v2, v3; if (v1,v2,v3)>0 then {push v1; push v2;} else {push v2; push v1;} push v3; insert v3; Шаг 2: Ввод v; until ((v,db,db+1)<0 or (dt-1,dt,c)<0) do { ввод v }; Шаг 3: until ((dt-1,dt,v)>0) do pop; push v; Шаг 4: until ((v,db,db+1)>0) do remove; insert v; Идти на Шаг 2.  8  Комментарии к статье  8 8  Обсудить в чате