convex_hull

関数 · 二次元点集合の凸包を構築する

template <class T>
std::vector<Point<T>> convex_hull(std::vector<Point<T>> points);

概要

二次元点集合の凸包を構築する

monotone chainにより、凸包上の点を巡回順で返す。

テンプレートパラメータ

パラメータ

戻り値

凸包上の点列

計算量

• 点数を $n$ として $O(n\log n)$