凸包
概要
点集合に対して，それを全て覆う最小の凸多角形を凸包といいます．釘打たれた木の板の外側に，外側から輪ゴムをかけたときにできる凸多角形です．
使い方
while の条件式について，同一直線上に 3 点以上存在する場合に ==CW なら全て含め，!=CCW なら両端以外を除きます．
実装
//@require intersection.cc
G andrewScan(G ps) {
int N = ps.size(), k = 0;
std::sort(ps.begin(), ps.end());
G res(N * 2);
for (int i = 0; i < N; i++) {
while (k >= 2 && ccw(res[k - 2], res[k - 1], ps[i]) == CW) k--;
res[k++] = ps[i];
}
int t = k + 1;
for (int i = N - 2; i >= 0; i--) {
while (k >= t && ccw(res[k - 2], res[k - 1], ps[i]) == CW) k--;
res[k++] = ps[i];
}
res.resize(k - 1);
return res;
}