verify/yosupo_library_checker/geometry/Static_Convex_Hull.test.cpp

• View this file on GitHub
• Last update: 2025-09-27 14:54:24+09:00
• Problem: https://judge.yosupo.jp/problem/static_convex_hull

Depends on

• Geometry/base.hpp
• Geometry/object/Point.hpp
• Geometry/object/Polygon.hpp
• Geometry/utility/Convex_Hull.hpp
• Geometry/utility/Counter_Clockwise.hpp
• template/bitop.hpp
• template/inout.hpp
• template/macro.hpp
• template/math.hpp
• template/template.hpp
• template/utility.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_convex_hull"

#include"../../../template/template.hpp"
#include"../../../Geometry/utility/Convex_Hull.hpp"

using namespace geometry;

void verify() {
    int N; cin >> N;
    vector<Point<ll>> points(N); cin >> points;

    auto X = Convex_Hull(points);

    cout << X.n << "\n";
    for (auto point: X.vertices) { cout << point << "\n"; }
}

int main() {
    int T; cin >> T;
    rep(T) { verify(); }
}

#line 1 "verify/yosupo_library_checker/geometry/Static_Convex_Hull.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_convex_hull"

#line 2 "template/template.hpp"

using namespace std;

// intrinstic
#include <immintrin.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

// utility
#line 2 "template/utility.hpp"

using ll = long long;

// a ← max(a, b) を実行する. a が更新されたら, 返り値が true.
template<typename T, typename U>
inline bool chmax(T &a, const U b){
    return (a < b ? a = b, 1: 0);
}

// a ← min(a, b) を実行する. a が更新されたら, 返り値が true.
template<typename T, typename U>
inline bool chmin(T &a, const U b){
    return (a > b ? a = b, 1: 0);
}
#line 59 "template/template.hpp"

// math
#line 2 "template/math.hpp"

// 除算に関する関数

// floor(x / y) を求める.
template<typename T, typename U>
T div_floor(T x, U y){ return (x > 0 ? x / y: (x - y + 1) / y); }

// ceil(x / y) を求める.
template<typename T, typename U>
T div_ceil(T x, U y){ return (x > 0 ? (x + y - 1) / y: x / y) ;}

// x を y で割った余りを求める.
template<typename T, typename U>
T mod(T x, U y){
    T q = div_floor(x, y);
    return x - q * y ;
}

// x を y で割った商と余りを求める.
template<typename T, typename U>
pair<T, T> divmod(T x, U y){
    T q = div_floor(x, y);
    return {q, x - q * y};
}

// 四捨五入を求める.
template<typename T, typename U>
T round(T x, U y){
    T q, r;
    tie (q, r) = divmod(x, y);
    return (r >= div_ceil(y, 2)) ? q + 1 : q;
}

// 指数に関する関数

// x の y 乗を求める.
ll intpow(ll x, ll y){
    ll a = 1;
    while (y){
        if (y & 1) { a *= x; }
        x *= x;
        y >>= 1;
    }
    return a;
}

// x の y 乗を z で割った余りを求める.
ll modpow(ll x, ll y, ll z){
    ll a = 1;
    while (y){
        if (y & 1) { (a *= x) %= z; }
        (x *= x) %= z;
        y >>= 1;
    }
    return a;
}

// x の y 乗を z で割った余りを求める.
template<typename T, typename U>
T modpow(T x, U y, T z) {
    T a = 1;
    while (y) {
        if (y & 1) { (a *= x) %= z; }

        (x *= x) %= z;
        y >>= 1;
    }

    return a;
}

// vector の要素の総和を求める.
ll sum(vector<ll> &X){
    ll y = 0;
    for (auto &&x: X) { y+=x; }
    return y;
}

// vector の要素の総和を求める.
template<typename T>
T sum(vector<T> &X){
    T y = T(0);
    for (auto &&x: X) { y += x; }
    return y;
}

// a x + b y = gcd(a, b) を満たす整数の組 (a, b) に対して, (x, y, gcd(a, b)) を求める.
tuple<ll, ll, ll> Extended_Euclid(ll a, ll b) {
    ll s = 1, t = 0, u = 0, v = 1;
    while (b) {
        ll q;
        tie(q, a, b) = make_tuple(div_floor(a, b), b, mod(a, b));
        tie(s, t) = make_pair(t, s - q * t);
        tie(u, v) = make_pair(v, u - q * v);
    }

    return make_tuple(s, u, a);
}

// floor(sqrt(N)) を求める (N < 0 のときは, 0 とする).
ll isqrt(const ll &N) { 
    if (N <= 0) { return 0; }

    ll x = sqrt(N);
    while ((x + 1) * (x + 1) <= N) { x++; }
    while (x * x > N) { x--; }

    return x;
}

// floor(sqrt(N)) を求める (N < 0 のときは, 0 とする).
ll floor_sqrt(const ll &N) { return isqrt(N); }

// ceil(sqrt(N)) を求める (N < 0 のときは, 0 とする).
ll ceil_sqrt(const ll &N) {
    ll x = isqrt(N);
    return x * x == N ? x : x + 1;
}
#line 62 "template/template.hpp"

// inout
#line 1 "template/inout.hpp"
// 入出力
template<class... T>
void input(T&... a){ (cin >> ... >> a); }

void print(){ cout << "\n"; }

template<class T, class... Ts>
void print(const T& a, const Ts&... b){
    cout << a;
    (cout << ... << (cout << " ", b));
    cout << "\n";
}

template<typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &P){
    is >> P.first >> P.second;
    return is;
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &P){
    os << P.first << " " << P.second;
    return os;
}

template<typename T>
vector<T> vector_input(int N, int index){
    vector<T> X(N+index);
    for (int i=index; i<index+N; i++) cin >> X[i];
    return X;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &X){
    for (auto &x: X) { is >> x; }
    return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &X){
    int s = (int)X.size();
    for (int i = 0; i < s; i++) { os << (i ? " " : "") << X[i]; }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &S){
    int i = 0;
    for (T a: S) {os << (i ? " ": "") << a; i++;}
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &S){
    int i = 0;
    for (T a: S) { os << (i ? " ": "") << a; i++; }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &S){
    int i = 0;
    for (T a: S) { os << (i ? " ": "") << a; i++; }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &S){
    int i = 0;
    for (T a: S) { os << (i ? " ": "") << a; i++; }
    return os;
}
#line 65 "template/template.hpp"

// macro
#line 2 "template/macro.hpp"

// マクロの定義
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define unless(cond) if (!(cond))
#define until(cond) while (!(cond))
#define loop while (true)

// オーバーロードマクロ
#define overload2(_1, _2, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload5(_1, _2, _3, _4, _5, name, ...) name

// 繰り返し系
#define rep1(n) for (ll i = 0; i < n; i++)
#define rep2(i, n) for (ll i = 0; i < n; i++)
#define rep3(i, a, b) for (ll i = a; i < b; i++)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define foreach1(x, a) for (auto &&x: a)
#define foreach2(x, y, a) for (auto &&[x, y]: a)
#define foreach3(x, y, z, a) for (auto &&[x, y, z]: a)
#define foreach4(x, y, z, w, a) for (auto &&[x, y, z, w]: a)
#define foreach(...) overload5(__VA_ARGS__, foreach4, foreach3, foreach2, foreach1)(__VA_ARGS__)
#line 68 "template/template.hpp"

// bitop
#line 2 "template/bitop.hpp"

// 非負整数 x の bit legnth を求める.
ll bit_length(ll x) {
    if (x == 0) { return 0; }
    return (sizeof(long) * CHAR_BIT) - __builtin_clzll(x);
}

// 非負整数 x の popcount を求める.
ll popcount(ll x) { return __builtin_popcountll(x); }

// 正の整数 x に対して, floor(log2(x)) を求める.
ll floor_log2(ll x) { return bit_length(x) - 1; }

// 正の整数 x に対して, ceil(log2(x)) を求める.
ll ceil_log2(ll x) { return bit_length(x - 1); }

// x の第 k ビットを取得する
int get_bit(ll x, int k) { return (x >> k) & 1; }

// x のビット列を取得する.
// k はビット列の長さとする.
vector<int> get_bits(ll x, int k) {
    vector<int> bits(k);
    rep(i, k) {
        bits[i] = x & 1;
        x >>= 1;
    }

    return bits;
}

// x のビット列を取得する.
vector<int> get_bits(ll x) { return get_bits(x, bit_length(x)); }
#line 2 "Geometry/utility/Convex_Hull.hpp"

#line 2 "Geometry/utility/Counter_Clockwise.hpp"

#line 2 "Geometry/object/Point.hpp"

#line 2 "Geometry/base.hpp"

#line 4 "Geometry/base.hpp"

namespace geometry {
    using Real = double long;
    const Real epsilon = 1e-9;
    const Real pi = acos(static_cast<Real>(-1));

    enum class Inclusion { OUT = -1, ON = 0, IN = 1 };
    enum class Direction_Relation { PARALLEL = 1, ORTHOGONAL = -1, CROSS = 0}; 

    inline int sign(const Real &r) { return r <= -epsilon ? -1 : r >= epsilon ? 1: 0; }
    inline int equal(const Real &a, const Real &b) { return sign(a - b) == 0; }
    inline int compare(const Real &a, const Real &b) { return sign(b - a); }

    inline int sign(const ll &r) { return r < 0 ? -1 : r > 0 ? 1 : 0; }
    inline int equal(const ll &a, const ll &b) { return sign(a - b) == 0; }
    inline int compare(const ll &a, const ll &b) { return sign(b - a); }

    inline int sign(const int &r) { return r < 0 ? -1 : r > 0 ? 1 : 0; }
    inline int equal(const int &a, const int &b) { return sign(a - b) == 0; }
    inline int compare(const int &a, const int &b) { return sign(b - a); }
};
#line 4 "Geometry/object/Point.hpp"

namespace geometry {
    template<typename R>
    class Point {
        public:
        R x, y;

        public:
        Point(): x(0), y(0) {}
        Point(R _x, R _y): x(_x), y(_y) {}

        // 加法
        Point& operator+=(const Point &B){
            x += B.x;
            y += B.y;
            return *this;
        }

        friend Point operator+(const Point &P, const Point &Q) { return Point(P) += Q; }

        // 減法
        Point& operator-=(const Point &B){
            x -= B.x;
            y -= B.y;
            return *this;
        }

        friend Point operator-(const Point &P, const Point &Q) { return Point(P) -= Q; }

        // スカラー倍
        Point& operator*=(const R &a){
            x *= a;
            y *= a;
            return *this;
        }

        friend Point operator*(const Point &P, const R &a) { return Point(P) *= a; }
        friend Point operator*(const R &a, const Point &P) { return Point(P) *= a; }

        Point& operator/=(const R &a){
            x /= a;
            y /= a;
            return *this;
        }

        friend Point operator/(const Point &P, const R &a) { return Point(P) /= a; }

        Point& operator*=(const Point &P){
            R x1 = P.x * x - P.y * y, y1 = P.y * x + P.x * y;
            x = x1;
            y = y1;
            return *this;
        }

        friend Point operator*(const Point &P, const Point<R> &Q) { return Point(P) *= Q; }

        friend istream& operator>>(istream &is, Point &P) {
            R a, b;
            is >> a >> b;
            P = Point(a, b);
            return is;
        }

        friend ostream& operator<<(ostream &os, const Point &P) {
            return os << P.x << " " << P.y;
        }

        inline R norm_2() const { return x * x + y * y; }
        inline double norm() const { return sqrt(norm_2()); }
        inline R dot(const Point B) const { return x * B.x + y * B.y; }
        inline R det(const Point B) const { return x * B.y - y * B.x; }

        inline Point<R> normalize() const { return *this / norm(); }
        inline Point<R> normal() const { return Point(-y, x); }

        inline Point<Real> rotate(double theta) const {
            Real alpha = sin(theta), beta = cos(theta);
            Real s = beta * x - alpha * y, t = alpha * x + beta * y;
            return Point(s, t);
        }
    };

    template<typename R>
    bool compare_x(const Point<R> &A, const Point<R> &B) { return equal(A.x, B.x) ? A.y < B.y : A.x < B.x; }

    template<typename R>
    bool compare_y(const Point<R> &A, const Point<R> &B) { return equal(A.y, B.y) ? A.x < B.x : A.y < B.y; }

    template<typename R>
    inline bool operator==(const Point<R> &A, const Point<R> &B) { return equal(A.x, B.x) && equal(A.y, B.y); }

    template<typename R>
    inline bool operator!=(const Point<R> &A, const Point<R> &B) { return !(A == B); }

    template<typename R>
    inline R dot(const Point<R> &A, const Point<R> &B) { return A.x * B.x + A.y * B.y; }

    template<typename R>
    inline R cross(const Point<R> &A, const Point<R> &B) { return A.x * B.y - A.y * B.x; }

    template<typename R>
    inline R norm_2(const Point<R> &P) { return dot(P, P); }

    template<typename R>
    inline double norm(const Point<R> &P) { return sqrt(norm_2(P)); }

    template<typename R>
    inline Real arg(const Point<R> &P) { return atan2(P.y, P.x); }
}
#line 4 "Geometry/utility/Counter_Clockwise.hpp"

namespace geometry {
    constexpr int COUNTER_CLOCKWISE = +1;
    constexpr int CLOCKWISE = -1;
    constexpr int ONLINE_BACK = -2;   // c-a-b
    constexpr int ONLINE_FRONT = +2;  // a-b-c
    constexpr int ON_SEGMENT = 0;     // a-c-b

    // A -> B -> C と進んだ時の進行方向を調べる (B 視点)
    // Input
    // A: 始点
    // B: 中継地点
    // C: 終点
    template<typename R>
    int Counter_Clockwise(const Point<R> &A, Point<R> B, Point<R> C) {
        B = B - A; C = C - A;
        if (sign(cross(B, C)) == +1) { return COUNTER_CLOCKWISE; }
        if (sign(cross(B, C)) == -1) { return CLOCKWISE; }
        if (sign(dot(B, C)) == -1) { return ONLINE_BACK; }
        if (norm_2(B) < norm_2(C)) { return ONLINE_FRONT; }
        return ON_SEGMENT;
    }
}
#line 2 "Geometry/object/Polygon.hpp"

#line 4 "Geometry/object/Polygon.hpp"

namespace geometry {
    template<typename R>
    struct Polygon {
        vector<Point<R>> vertices;
        int n;

        Polygon() = default;
        Polygon(const vector<Point<R>> &_vertices): vertices(_vertices), n(_vertices.size()) {}
    };

    template<typename R>
    R Area(const Polygon<R> &X) {
        R area = cross(X.vertices[X.n - 1], X.vertices[0]);
        for (int i = 0; i < X.n - 1; i++) {
            area += cross(X.vertices[i], X.vertices[i + 1]);
        }

        return abs(area) / 2;
    }
}
#line 5 "Geometry/utility/Convex_Hull.hpp"

namespace geometry {
    template<typename R>
    Polygon<R> Convex_Hull(vector<Point<R>> points, bool strict = true) {
        // 前処理
        sort(points.begin(), points.end(), compare_x<R>);
        points.erase(unique(points.begin(), points.end()), points.end());

        int n = points.size();

        if (n <= 2) { return Polygon(points); }

        int k = 0;
        vector<Point<R>> vertices(2 * n);
        auto is_valid = [&](const int i) -> bool { 
            int d = Counter_Clockwise(vertices[k - 2], vertices[k - 1], points[i]);
            return (d == COUNTER_CLOCKWISE || (!strict && d == ONLINE_FRONT));
        };

        for (int i = 0; i < n; vertices[k++] = points[i++]) {
            if (!vertices.empty() && vertices.back() == points[i]) { vertices.pop_back(); }

            while(k >= 2 && !is_valid(i)) {
                k--;
            }
        }

        for (int i = n - 2, t = k + 1; i >= 0; vertices[k++] = points[i--]) {
            if (!vertices.empty() && vertices.back() == points[i]) { vertices.pop_back(); }

            while (k >= t && !is_valid(i)) {
                k--;
            }
        }

        vertices.resize(k - 1);
        return Polygon(vertices);
    }
}
#line 5 "verify/yosupo_library_checker/geometry/Static_Convex_Hull.test.cpp"

using namespace geometry;

void verify() {
    int N; cin >> N;
    vector<Point<ll>> points(N); cin >> points;

    auto X = Convex_Hull(points);

    cout << X.n << "\n";
    for (auto point: X.vertices) { cout << point << "\n"; }
}

int main() {
    int T; cin >> T;
    rep(T) { verify(); }
}

Back to top page