Алгоритм Грэхэма-Эндрю

Построение выпуклой оболочки, не должно занимать много времени. А надо признать, все приведенные мной реализации решения задачи построения выпуклой оболочки страдают большим объемом.

Реализация данного алгоритма на e-maxx’e порадовала свой лаконичностью.
Но увиденное у indy256 порадовала еще больше: 

1. vector<point> convexHull(vector<point> p) {
2.   int n = p.size();
3.   if (n <= 1)
4.     return p;
5.   int k = 0;
6.   sort(p.begin(), p.end());
7.   vector<point> q(n * 2);
8.   for (int i = 0; i < n; q[k++] = p[i++])
9.     for (; k >= 2 && !cw(q[k - 2], q[k - 1], p[i]); --k)
10.       ;
11.   for (int i = n - 2, t = k; i >= 0; q[k++] = p[i--])
12.     for (; k > t && !cw(q[k - 2], q[k - 1], p[i]); --k)
13.       ;
14.   q.resize(k - 1 - (q[0] == q[1]));
15.   return q;
16. }

* This source code was highlighted with Source Code Highlighter.

Очень крутая реализация =). Возьмем ее на вооружение, как и весь сайт indy256