test/geometry/convex_hull.test.cpp

• View this file on GitHub
• Last update: 2023-10-26 02:38:17+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_4_A

Depends on

• geometry/convex_hull.hpp

Code

#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_4_A"

#include "geometry/convex_hull.hpp"

#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>

namespace ebi {

using i64 = std::int64_t;

void main_() {
    int n;
    std::cin >> n;
    std::vector<Point<i64>> poly(n);
    for (auto& [x, y] : poly) {
        std::cin >> x >> y;
    }
    auto ch = convex_hull(n, poly, true);
    int m = ch.size();
    int idx = 0;
    for (int i = 0; i < m; i++) {
        if (ch[i].y < ch[idx].y) {
            idx = i;
        } else if (ch[i].y == ch[idx].y) {
            if (ch[i].x < ch[idx].x) {
                idx = i;
            }
        }
    }
    std::cout << m << '\n';
    for (int i = 0; i < m; i++) {
        auto [x, y] = ch[(i + idx) % m];
        std::cout << x << " " << y << '\n';
    }
}

}  // namespace ebi

int main() {
    std::cout << std::fixed << std::setprecision(15);
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ebi::main_();
}

#line 1 "test/geometry/convex_hull.test.cpp"
#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_4_A"

#line 2 "geometry/convex_hull.hpp"

#include <algorithm>

#include <vector>


/*
    reference: プログラミングコンテストチャレンジブック 第2版 p234
    verify:    https://atcoder.jp/contests/typical90/submissions/24974484
*/

namespace ebi {

template <class T> struct Point {
    T x, y;

    Point &operator+=(const Point &rhs) noexcept {
        x += rhs.x;
        y += rhs.y;
        return *this;
    }

    Point &operator-=(const Point &rhs) noexcept {
        x -= rhs.x;
        y -= rhs.y;
        return *this;
    }

    Point operator-(const Point &rhs) const noexcept {
        return Point(*this) -= rhs;
    }

    T det(const Point &rhs) const noexcept {
        return x * rhs.y - y * rhs.x;
    }
};

template <class T>
std::vector<Point<T>> convex_hull(int n, std::vector<Point<T>> p,
                                  bool on = false) {
    std::sort(p.begin(), p.end(), [](const Point<T> &a, const Point<T> &b) {
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    });
    std::vector<Point<T>> g1, g2;
    int k1 = 0, k2 = 0;
    for (int i = 0; i < n; i++) {
        while (k1 > 1 &&
               (g1[k1 - 1] - g1[k1 - 2]).det(p[i] - g1[k1 - 1]) <= 0) {
            if (on && (g1[k1 - 1] - g1[k1 - 2]).det(p[i] - g1[k1 - 1]) == 0)
                break;
            g1.pop_back();
            k1--;
        }
        while (k2 > 1 &&
               (g2[k2 - 1] - g2[k2 - 2]).det(p[i] - g2[k2 - 1]) >= 0) {
            if (on && (g2[k2 - 1] - g2[k2 - 2]).det(p[i] - g2[k2 - 1]) == 0)
                break;
            g2.pop_back();
            k2--;
        }
        g1.push_back(p[i]);
        k1++;
        g2.push_back(p[i]);
        k2++;
    }
    std::vector<Point<T>> ch(k1 + k2 - 2);
    for (int i = 0; i < k1; i++) {
        ch[i] = g1[i];
    }
    for (int i = k2 - 2; i > 0; i--) {
        ch[k1 + k2 - i - 2] = g2[i];
    }
    return ch;
}

}  // namespace ebi
#line 5 "test/geometry/convex_hull.test.cpp"

#line 7 "test/geometry/convex_hull.test.cpp"
#include <cstdint>
#include <iomanip>
#include <iostream>
#line 11 "test/geometry/convex_hull.test.cpp"

namespace ebi {

using i64 = std::int64_t;

void main_() {
    int n;
    std::cin >> n;
    std::vector<Point<i64>> poly(n);
    for (auto& [x, y] : poly) {
        std::cin >> x >> y;
    }
    auto ch = convex_hull(n, poly, true);
    int m = ch.size();
    int idx = 0;
    for (int i = 0; i < m; i++) {
        if (ch[i].y < ch[idx].y) {
            idx = i;
        } else if (ch[i].y == ch[idx].y) {
            if (ch[i].x < ch[idx].x) {
                idx = i;
            }
        }
    }
    std::cout << m << '\n';
    for (int i = 0; i < m; i++) {
        auto [x, y] = ch[(i + idx) % m];
        std::cout << x << " " << y << '\n';
    }
}

}  // namespace ebi

int main() {
    std::cout << std::fixed << std::setprecision(15);
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ebi::main_();
}

Back to top page