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

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

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

• ACMP #374 — Выпуклая оболочка - 2
• MCCME #290 — Выпуклая оболочка (периметр и площадь)
• MCCME #638 — Выпуклая оболочка - периметр

Ссылки

• informatics.mccme.ru — Курс «Геометрия» — часть 3
• www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts
• Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости
• Algos — Graham scan