convex-hull.cpp

convex-hull.cpp

#include <algorithm>
#include <concepts>
#include <iostream>
#include <ranges>
#include <type_traits>
#include <vector>
#define self (*this)
#define repeat(i, n) for (remove_cv_t<remove_reference_t<decltype(n)>> i = 0; i < (n); ++i)

using namespace std;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;

template <typename T>
concept signed_arithmetic = signed_integral<T> || floating_point<T>;

template <signed_arithmetic T>
using product_expand = conditional_t<floating_point<T>, T,
                       conditional_t<is_same_v<T, i8>, i16,
                       conditional_t<is_same_v<T, i16>, i32,
                       conditional_t<is_same_v<T, i32>, i64,
                       i128>>>>;

template <typename C, typename T>
concept arithmetic_not_smaller_than = signed_arithmetic<C> && signed_arithmetic<T> && !(signed_integral<C> && floating_point<T>) &&
        (floating_point<C> && signed_integral<T> || (numeric_limits<C>::max() >= numeric_limits<T>::max() && numeric_limits<C>::lowest() <= numeric_limits<C>::lowest()));

template <signed_arithmetic T>
struct Vec2d final {
    T x;
    T y;

    using element_t = T;

    constexpr Vec2d() noexcept = default;
    constexpr Vec2d(T x, T y) noexcept : x(x), y(y) {}

    [[nodiscard]] constexpr bool operator==(const Vec2d& other) const noexcept = default;

    [[nodiscard]] constexpr Vec2d operator+(const Vec2d& other) const noexcept {
        return Vec2d(self.x + other.x, self.y + other.y);
    }
    constexpr Vec2d& operator+=(const Vec2d& other) const noexcept {
        self.x += other.x;
        self.y += other.y;
        return self;
    }
    [[nodiscard]] constexpr Vec2d operator-(const Vec2d& other) const noexcept {
        return Vec2d(self.x - other.x, self.y - other.y);
    }
    constexpr Vec2d& operator-=(const Vec2d& other) const noexcept {
        self.x -= other.x;
        self.y -= other.y;
        return self;
    }
    [[nodiscard]] constexpr Vec2d operator*(const T& other) const noexcept {
        return Vec2d(self.x * other, self.y * other);
    }
    constexpr Vec2d& operator*=(const T& other) const noexcept {
        self.x *= other;
        self.y *= other;
        return self;
    }
    [[nodiscard]] friend constexpr Vec2d operator*(const T& lhs, const Vec2d& rhs) {
        return Vec2d(lhs * rhs.x, lhs * rhs.y);
    }
    [[nodiscard]] constexpr Vec2d operator/(const T& other) const noexcept {
        return Vec2d(self.x / other, self.y / other);
    }
    constexpr Vec2d& operator/=(const T& other) const noexcept {
        self.x /= other;
        self.y /= other;
        return self;
    }
    [[nodiscard]] friend constexpr Vec2d operator/(const T& lhs, const Vec2d& rhs) {
        return Vec2d(lhs / rhs.x, lhs / rhs.y);
    }
    [[nodiscard]] constexpr Vec2d operator-() const noexcept {
        return Vec2d(-self.x, -self.y);
    }

    template <arithmetic_not_smaller_than<T> C = product_expand<T>>
    [[nodiscard]] constexpr C sqr() const noexcept {
        return static_cast<C>(self.x) * self.x + static_cast<C>(self.y) * self.y;
    }
    template <arithmetic_not_smaller_than<T> C = product_expand<T>>
    [[nodiscard]] constexpr C dst_sqr(const Vec2d& other) const noexcept {
        return (self - other).template sqr<C>();
    }
    template <arithmetic_not_smaller_than<T> C = product_expand<T>>
    requires signed_integral<C> || floating_point<C>
    [[nodiscard]] constexpr C dot(const Vec2d& other) const noexcept {
        return static_cast<C>(self.x) * other.x + static_cast<C>(self.y) * other.y;
    }
    template <arithmetic_not_smaller_than<T> C = product_expand<T>>
    [[nodiscard]] constexpr C cross(const Vec2d& other) const noexcept {
        return static_cast<C>(self.x) * other.y - static_cast<C>(self.y) * other.x;
    }
};

template <ranges::random_access_range R, arithmetic_not_smaller_than<typename ranges::range_value_t<R>::element_t> C = product_expand<typename ranges::range_value_t<R>::element_t>>
    requires is_same_v<ranges::range_value_t<R>, Vec2d<typename ranges::range_value_t<R>::element_t>>
constexpr ranges::borrowed_subrange_t<R> convex_hull(R&& points) noexcept {
    if (ranges::empty(points)) return ranges::borrowed_subrange_t<R>(points);
    auto pivot = *ranges::min_element(points, [](const auto& a, const auto& b) -> bool {
        return a.y < b.y || a.y == b.y && a.x < b.x;
    });
    ranges::sort(points, [&](const auto& a, const auto& b) -> bool {
        return a == pivot || b != pivot && ((a - pivot).template cross<C>(b - pivot) > 0 || (a - pivot).template cross<C>(b - pivot) == 0 && (abs(a.x - pivot.x) > abs(b.x - pivot.x) || abs(a.y - pivot.y) > abs(b.y - pivot.y)));
    });
    auto [points_last, _] = ranges::unique(points, [&](const auto& a, const auto& b) -> bool {
        return a != pivot && b != pivot && (a - pivot).template cross<C>(b - pivot) == 0;
    });
    auto hull_first = ranges::begin(points);
    auto hull_last = hull_first + 1;

    for (auto points_first = hull_last; points_first != points_last; ++points_first) {
        const auto& cur = *points_first;
        while (hull_last - hull_first >= 2) {
            const auto& back = hull_last[-1];
            const auto& back_back = hull_last[-2];
            if ((back - back_back).template cross<C>(cur - back) <= 0) {
                --hull_last;
            } else {
                break;
            }
        }
        if (hull_last != points_first) {
            *hull_last = move(cur);
        }
        ++hull_last;
    }
    while (hull_last - hull_first >= 2) {
        const auto& cur = pivot;
        const auto& back = hull_last[-1];
        const auto& back_back = hull_last[-2];
        if ((back - back_back).cross(cur - back) <= 0) {
            --hull_last;
        } else {
            break;
        }
    }

    return ranges::borrowed_subrange_t<R>(hull_last, ranges::end(points));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    i32 n; cin >> n;
    vector<Vec2d<i32>> points(n);
    repeat(i, n) {
        cin >> points[i].x >> points[i].y;
    }

    {
        const auto [first, last] = convex_hull(points);
        points.erase(first, last);
    }

    cout << points.size() << '\n';
    return 0;
}

I'm in love with your code.