Просмотр кода страницы Выпуклая оболочка

* Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку O.
* Сортируем остальные почки по полярному углу от O. Точка A должна идти раньше точки B, если поворот от вектора OA к вектору OB происходит по часовой стрелке (косое произведение положительно). Если OA и OB коллинеарны, то раньше идёт точка, ближайшая к O.
* Добавляем точку O в оболочку.
* Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.

{|
| width="50%"  |  

 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 &lt; b.y || (a.y == b.y && a.x &lt; 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) &gt; 0 || (va.cross(vb) == 0 && va.length() < vb.length());
 }

| width="10px" | 
| width="50%"  | 
 
  vector&lt;P&gt; convexHull(vector&lt;P&gt; &p) {
     sort(p.begin(), p.end(), compareByCoords);
     o = p[0];
     sort(p.begin() + 1, p.end(), compareByAngle);
 
     vector&lt;P&gt; hull;
     for (int i = 0; i &lt; p.size(); i++) {
         while (hull.size() &gt;= 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) &lt;= 0)
                 hull.pop_back();
             else
                 break;
         }
         hull.push_back(p[i]);
     }
     return hull;
 }
 
|}

== Ссылки на задачи ==
* [http://acmp.ru/?main=task&id_task=374 ACMP #374 &mdash; Выпуклая оболочка - 2]
* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=290 MCCME #290 &mdash; Выпуклая оболочка (периметр и площадь)]
* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=638 MCCME #638 &mdash; Выпуклая оболочка - периметр]

== Ссылки ==
* [http://informatics.mccme.ru/course/view.php?id=22 informatics.mccme.ru &mdash; Курс &laquo;Геометрия&raquo; &mdash; часть 3]
* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures &mdash; 2.1 Elementary Sorts]
* [http://e-maxx.ru/bookz/files/andreeva.pdf Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости]
* [http://visualgo.net/geometry.html VisuAlgo &mdash; (Computational) Geometry]
* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp Algos &mdash; Graham scan]

[[Категория:Геометрия]]