凸包(Convex Hull)
(geometry/convex_hull.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

整数座標点集合の凸包を Andrew’s monotone chain で求める。 計算量は $O(N log N)$。

できること

• vector<pair<ll, ll>> convex_hull(vector<pair<ll, ll>> ps) 点集合の凸包の頂点を反時計回り順で返す。辺上の中間点と重複点は除く

使い方

点列を vector<pair<ll, ll>> で渡して使う。

実装上の補足

返り値は辞書順最小の点から始まる反時計回り順になる。 点数が 0, 1, 2 のときは重複を除いた結果をそのまま返す。

Verified with

• test/yosupo_static_convex_hull.test.cpp

Code

using IntPoint = pair<ll, ll>;

ll cross(IntPoint a, IntPoint b, IntPoint c) {
    b.first -= a.first;
    b.second -= a.second;
    c.first -= a.first;
    c.second -= a.second;
    return b.first * c.second - b.second * c.first;
}

vector<IntPoint> convex_hull(vector<IntPoint> ps) {
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    int n = ps.size();
    if (n <= 2) return ps;

    vector<IntPoint> ch(2 * n);
    int k = 0;
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
        ch[k++] = ps[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; --i) {
        while (k >= t && cross(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
        ch[k++] = ps[i];
    }
    ch.resize(k - 1);
    return ch;
}

/**
 * @brief 凸包(Convex Hull)
 */

#line 1 "geometry/convex_hull.cpp"
using IntPoint = pair<ll, ll>;

ll cross(IntPoint a, IntPoint b, IntPoint c) {
    b.first -= a.first;
    b.second -= a.second;
    c.first -= a.first;
    c.second -= a.second;
    return b.first * c.second - b.second * c.first;
}

vector<IntPoint> convex_hull(vector<IntPoint> ps) {
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    int n = ps.size();
    if (n <= 2) return ps;

    vector<IntPoint> ch(2 * n);
    int k = 0;
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
        ch[k++] = ps[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; --i) {
        while (k >= t && cross(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
        ch[k++] = ps[i];
    }
    ch.resize(k - 1);
    return ch;
}

/**
 * @brief 凸包(Convex Hull)
 */

Back to top page