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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
  • Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку 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) {
    sort(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), ac(a, p);
            if (ab.crossProduct(ap) <= 0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(p);
    }
    return hull;
}

Ссылки

Теория:

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

Код:

Задачи: