ориентированного ребра}
else begin
h:=САМАЯ ДАЛЬНЯЯ ТОЧКА(S,w,r);
S1:=[точки множества S, расположенные слева от wh или на ней];
S2:=[точки множества S, расположенные слева от hr или на ней];
U1:=Bpo(S1,w,h);
U2:=Bpo(S2,h,r);
Bpo:=U1+U2;{+ означает сцепление списков U1 и U2}
end;
end;
Четвертый метод. Заданы два выпуклых многоугольника Q1 и Q2. Найти выпуклую оболочку их объединения. Метод обработки.
Шаг 1. Находим некоторую внутреннюю точку t многоугольника Q1(центр масс трех любых вершин Q1).
Шаг 2. Определяем, является ли точка t внутренней точкой многоугольника Q2 (За время, пропорциональное O(N)). Если точка t не является внутренней точкой Q2, то переходим к шагу 4.
Шаг 3. Точка t является внутренней точкой Q2. Вершины как Q1, так и Q2 упорядочены в соответствии со значением полярного угла относительно точки t. За время, пропорциональное O(N) получаем упорядоченный список вершин как Q1, так и Q2 путем слияния списков вершин этих многоугольников.
