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

• Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку 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;
    }
};

Point o;
bool compareByAngle(const Point &a, const Point &b) {
    Point oa(o, a), ob(o, b);
    return oa.crossProduct(ob) > 0 || oa.crossProduct(ob) == 0 && oa.length() < ob.length();
}

vector<Point> convexHull(vector<Point> &points) {
    sort(points.begin(), points.end());
    o = points[0];

    sort(points.begin() + 1, points.end(), compareByAngle);

    vector<Point> hull;
    for (int i = 0; i < points.size(); i++) {
        while (hull.size() >= 2) {
            Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1], &c = points[i];
            Point ab(a, b), ac(a, c);
            if (ab.crossProduct(ac) <= 0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(points[i]);
    }
    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