凸包 (Andrew's Monotone Chain)

解説

Andrew's Monotone Chain は凸包を求めるアルゴリズムで，Graham Scan における角度計算を ccw に置き換えてロバストにしたものである．

点列を x 座標でソートした後，下側凸包と上側凸包を別々に求め，併合して凸包を構成する．下側凸包を求めるときは点集合を左から右に見ていき，進行方向が左側であるような最も右よりの点を取っていく．上側凸包の場合は右から左に見ていく以外は全く同一である．進行方向に対して同一直線上にある場合は，最も近いものを取ることで凸包上にある点を取りこぼすことなく凸包に入れることができる．

使い方

vector<point> convex_hull(vector<point> ps)

点集合 ps に対してその凸包を求める．ps は三点以上あることを仮定する．

計算量

O(n log n)．

ソースコード

vector<point> convex_hull(vector<point> ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  vector<point> ch(2*n);
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  ch.resize(k-1);
  return ch;
}

Verified

• UVA 109 (SCUD Busters), 6 MS, -- KB