geometry/convex-hull.hpp

• View this file on GitHub
• Last update: 2026-08-30 15:33:14+09:00
• Include: #include "geometry/convex-hull.hpp"

Depends on

• geometry/base.hpp
• geometry/cross.hpp

Required by

• 幾何ライブラリ (geometry/geometry.hpp)

Verified with

• test/mytest/geometry/geometry.test.cpp

Code

#pragma once

#include <algorithm>
#include <vector>

#include "cross.hpp"

namespace geometry {
    // 凸包 O(NlogN)
    inline std::vector<Point> ConvexHull(std::vector<Point> p) {
        int n = (int)p.size(), k = 0;
        std::sort(p.begin(), p.end(), [](const Point &a, const Point &b) {
            return (a.real() != b.real() ? a.real() < b.real()
                                         : a.imag() < b.imag());
        });
        std::vector<Point> ch(2 * n);
        // 一直線上の3点を含める -> (< -EPS)
        // 含め無い -> (< EPS)
        for(int i = 0; i < n; ch[k++] = p[i++]) { // lower
            while(k >= 2 &&
                  cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)
                --k;
        }
        for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) { // upper
            while(k >= t &&
                  cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)
                --k;
        }
        ch.resize(k - 1);
        return ch;
    }
} // namespace geometry

#line 2 "geometry/convex-hull.hpp"

#include <algorithm>
#include <vector>

#line 2 "geometry/cross.hpp"

#line 2 "geometry/base.hpp"

#include <cmath>
#include <complex>

namespace geometry {
    // Point : 複素数型を位置ベクトルとして扱う
    // 実軸(real)をx軸、挙軸(imag)をy軸として見る
    using D = long double;
    using Point = std::complex<D>;
    const D EPS = 1e-7;
    const D PI = std::acos(D(-1));

    inline bool equal(const D &a, const D &b) { return std::fabs(a - b) < EPS; }
} // namespace geometry
#line 4 "geometry/cross.hpp"

namespace geometry {
    // 外積(cross product) : a×b = |a||b|sinΘ
    inline D cross(const Point &a, const Point &b) {
        return (a.real() * b.imag() - a.imag() * b.real());
    }
} // namespace geometry
#line 7 "geometry/convex-hull.hpp"

namespace geometry {
    // 凸包 O(NlogN)
    inline std::vector<Point> ConvexHull(std::vector<Point> p) {
        int n = (int)p.size(), k = 0;
        std::sort(p.begin(), p.end(), [](const Point &a, const Point &b) {
            return (a.real() != b.real() ? a.real() < b.real()
                                         : a.imag() < b.imag());
        });
        std::vector<Point> ch(2 * n);
        // 一直線上の3点を含める -> (< -EPS)
        // 含め無い -> (< EPS)
        for(int i = 0; i < n; ch[k++] = p[i++]) { // lower
            while(k >= 2 &&
                  cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)
                --k;
        }
        for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) { // upper
            while(k >= t &&
                  cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)
                --k;
        }
        ch.resize(k - 1);
        return ch;
    }
} // namespace geometry

Back to top page