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

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

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

Ссылки

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

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

Ссылки

Навигация

Поиск