add_to_other_convex_hull

void add_to_other_convex_hull(Points & hull, const Point & p){
//  Добавляет новую точку к выпуклой оболочке, состоящей больше, чем из двух точек

    int begin=-1, end=-1, len=0, i=0, j=1, n = hull.size();
    double sq;

//  Ищем минимальный отрезок [i, j] (i и j - соседние вершины) по следующим правилам:
//  1) Ориентированная площадь треугольника с вершинами i-p-j не отрицательна
//  2) Точка p не принадлежит отрезку, образованному вершинами i-j
    do {
        sq = square_triangle(hull[i], p, hull[j]);
        if (sq == 0 && in_interval(hull[i], hull[j], p)) return; // (условие 2)
        if (sq >= 0) break; // (условие 1)
        inc(i, n);
        inc(j, n);
    } while (i != 0);

//  Если отрезок не найден, то точку добавлять не нужно:
    if (i == 0) return;

//  Затем необходимо расширить найденный отрезок из вершин выпуклой оболочки до максимально возможного

//  Расширение вправо
    i = j = end; inc(j, n);
    while (square_triangle(hull[i], p, hull[j]) >= 0){
        end = j;
        inc(i, n);
        inc(j, n);
    }

//  Расширение влево
    i = j = begin; dec(i, n);
    while (square_triangle(hull[i], p, hull[j]) >= 0){
        begin = i;
        dec(i, n);
        dec(j, n);
    }

//  Теперь найденный отрезок выпуклой оболочки необходимо модифицировать

//  Вычисляем длину отрезка [begin, end] по модулю n:
    mod(len = end-begin, n);

    if (begin > end && end != 0) { // Если начало отрезка больше конца
        shift_points_left(hull, end); // То сдвигаем все элементы оболочки влево на величину, равную концу отрезка
        begin -= end;
        end -= end;
    }

//  Крайние точки мы должны оставить в покое, поэтому:
    inc(begin, n); // Увеличиваем на единицу начало отрезка
    dec(end, n); // Уменьшаем на единицу конец отрезка

    switch (len){ // В зависимости от длины отрезка
        case 0: return; // Ничего не делаем, если длина отрезка равна 0
        case 1: hull.emplace(hull.begin()+begin, p); break; // Вставляем новую точку, если длина отрезка равна 1
        case 2: hull[begin] = p; break; // Заменяем точку, расположенную вначале отрезка, на новую точку
        default:
            hull[begin] = p; // Заменяем точку вначале отрезка на новую точку
            inc(begin, n); // Увеличиваем начало отрезка
            erase_from_points(hull, begin, end); // Вырезаем все остальные точки из отрезка [begin, end]
            break;
    }
}