Выпуклая оболочка

Выпуклая оболочка набора точек - наименьший выпуклый многоугольник, который их все содержит. Через неё решаются диаметр множества, минимальная описанная фигура, проверка на выпуклость и половина задач про «крайние» точки.

Обход Эндрю

Отсортируем точки по $x$, при равных - по $y$. Построим нижнюю цепь: идём слева направо и держим стек, выбрасывая из него точку, если тройка перестала поворачивать влево. Потом то же самое справа налево - получится верхняя цепь.

auto build = [&](const std::vector<P> &arr) {
    std::vector<P> st;
    for (const P &q : arr) {
        while (st.size() >= 2 && cross(st[st.size()-1] - st[st.size()-2], q - st[st.size()-2]) <= 0)
            st.pop_back();
        st.push_back(q);
    }
    return st;
};
std::sort(p.begin(), p.end());
auto lower = build(p);
std::reverse(p.begin(), p.end());
auto upper = build(p);
lower.pop_back(); upper.pop_back();
lower.insert(lower.end(), upper.begin(), upper.end());   // обход против часовой стрелки

Сложность - $O(n\log n)$, и почти всё это время уходит на сортировку: сами проходы линейны, потому что каждая точка кладётся в стек один раз и выбрасывается не больше одного раза.

Строгий знак или нестрогий

Единственное место, где придётся выбирать: сравнение <= 0 или < 0.

условие	что получится
<= 0	точки на сторонах выбрасываются, остаются только «углы»
< 0	точки на сторонах остаются в ответе

Обе версии верны, но отвечают на разные вопросы. Если задача просит «вершины оболочки», нужен первый вариант; если «все точки, лежащие на границе» - второй. Прочитайте условие внимательно: это самый частый источник неверного ответа в задачах на оболочку.

Проверка себя

У правильной оболочки два свойства, и оба легко проверить перебором на маленьких тестах:

• каждая точка набора лежит внутри или на границе;
• каждая сторона оболочки опорная: строго слева от неё нет ни одной точки.

Проверено на 3000 случайных наборов до 12 точек с координатами до 8 - оба свойства выполняются.

Сколько вершин ожидать

У случайных точек в квадрате на оболочке оказывается лишь $O(\log n)$ вершин, у точек в круге - $O(n^{1/3})$. Поэтому «оболочка почти всегда маленькая» - и поэтому же большой выпуклый многоугольник нельзя получить, взяв оболочку случайных точек: его строят из точек на окружности.

Есть и жёсткая граница: у выпуклого многоугольника с целыми вершинами в квадрате $N \times N$ вершин не больше $\Theta(N^{2/3})$. При $N = 10^6$ это около десяти тысяч.

Смежное

• Векторное произведение;
• Вращающиеся калиперы.