понедельник, 17 января 2011 г.

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


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

Реализация данного алгоритма на 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

Комментариев нет:

Отправить комментарий