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

Материал из Олимпиадное программирование в УлГТУ
Перейти к: навигация, поиск
  • Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку O.
  • Сортируем остальные почки по полярному углу от O. Точка A должна идти раньше точки B, если поворот от вектора OA к вектору OB происходит против часовой стрелки (косое произведение положительно). Если OA и OB коллинеарны, то раньше идёт точка, ближайшая к O.
  • Добавляем точку O в оболочку.
  • Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.
struct P { 
    double x, y; 
    P(double X, double Y) : x(X), y(Y) {} 
    double length() const {
        return sqrt(y * y + x * x);
    } 
    double cross(const P &p) const {
        return x * p.y - y * p.x;
    } 
};

bool compareByCoords(const P &a, const P &b) {
    return a.y < b.y || (a.y == b.y && a.x < b.x);
}

P o(0, 0);
bool compareByAngle(const P &a, const P &b) {
    P va(a.x - o.x, a.y - o.y), vb(b.x - o.x, b.y - o.y);
    return va.cross(vb) > 0 || (va.cross(vb) == 0 && va.length() < vb.length());
}
 vector<P> convexHull(vector<P> &p) {
    sort(p.begin(), p.end(), compareByCoords);
    o = p[0];
    sort(p.begin() + 1, p.end(), compareByAngle);

    vector<P> hull;
    for (int i = 0; i < p.size(); i++) {
        while (hull.size() >= 2) {
            P &o = hull[hull.size() - 2], &a = hull[hull.size() - 1], &b = p[i];
            P oa(a.x - o.x, a.y - o.y), ob(b.x - o.x, b.y - o.y);
            if (oa.cross(ob) <= 0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(p[i]);
    }
    return hull;
}

Ссылки на задачи

Ссылки