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

• Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку O.
• Сортируем остальные почки по полярному углу от O. Точка A должна идти раньше точки B, если поворот от вектора OA к вектору OB происходит против часовой стрелки (косое произведение положительно). Если OA и OB коллинеарны, то раньше идёт точка, ближайшая к O.
• Добавляем точку O в оболочку.
• Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.

struct Point {
    double x, y;

    Point() {}

    Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}

    bool operator < (const Point &that) const {
        return y < that.y || y == that.y && x < that.x;
    }

    double length() const {
        return hypot(x, y);
    }

    double crossProduct(const Point &that) const {
        return x * that.y - y * that.x;
    }
};

vector<Point> convexHull(vector<Point> &points) {
    nth_element(points.begin(), points.begin(), points.end());
    sort(points.begin() + 1, points.end(), [&](Point &a, Point &b) {
        Point &o = points[0], oa(o, a), ob(o, b);
        return oa.crossProduct(ob) > 0 || oa.crossProduct(ob) == 0 && oa.length() < ob.length();
    });

    vector<Point> hull;
    for (Point &p : points) {
        while (hull.size() >= 2) {
            Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1];
            Point ab(a, b), ap(a, p);
            if (ab.crossProduct(ap) <= 0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(p);
    }
    return hull;
}

Ссылки

Теория:

• e-maxx.ru — Построение выпуклой оболочки обходом Грэхэма
• cp-algorithms.com — Convex Hull construction using Graham's Scan
• algorithmica.org — Выпуклая оболочка: 1, 2
• Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости
• www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts
• usaco.guide — Convex Hull

Демонстрация:

• VisuAlgo — Convex Hull

Код:

• indy256/codelibrary/cpp/geometry/convex_hull.cpp
• ADJA/algos/Geometry/convex_hull_graham_scan.cpp
• kevin-wayne/algs4/GrahamScan.java

Задачи:

• informatics.mccme.ru — Курс «Геометрия» — часть 3
• MCCME #290 — Выпуклая оболочка (периметр и площадь)
• MCCME #638 — Выпуклая оболочка - периметр
• ACMP #374 — Выпуклая оболочка - 2