マンハッタン距離で最も近い点への距離の列挙
(library/graph/manhattan_minimum_distances.hpp)

• View this file on GitHub
• Last update: 2022-06-14 00:04:46+09:00
• Include: #include "library/graph/manhattan_minimum_distances.hpp"

マンハッタン距離で最も近い点への距離の列挙

$N$ 個の点 $(x_i,y_i)$ が与えられるので，以下で定まる $d _ i$ を全ての $i$ に対して $O(N\log N)$ 時間で計算する．

\[d _ i = \min _ {j \neq i} |x _ i - x _ j| + |y _ i - y _ j|\]

Depends on

• Fenwick Tree Prefix (library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp)

Code

#ifndef SUISEN_MANHATTAN_MINIMUM_DISTANCES
#define SUISEN_MANHATTAN_MINIMUM_DISTANCES

#include <algorithm>
#include <limits>
#include <numeric>
#include <vector>

#include "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp"

namespace suisen {
    namespace internal::manhattan_minimum_distances {
        template <typename T>
        T op(T x, T y) { return std::max(x, y); };
        template <typename T>
        T e() { return std::numeric_limits<T>::min(); };
        template <typename T>
        using PrefixMaxQuery = FenwickTreePrefix<T, op<T>, e<T>>;
    } // namespace internal::manhattan_minimum_distances

    template <typename T>
    std::vector<T> manhattan_minimum_distances(std::vector<std::pair<T, T>> points) {
        using namespace internal::manhattan_minimum_distances;

        const int n = points.size();
        std::vector<int> p(n);
        std::iota(p.begin(), p.end(), 0);

        std::vector<T> res(n, std::numeric_limits<T>::max());

        auto sweep = [&] {
            std::sort(
                p.begin(), p.end(),
                [&points](int i, int j) {
                    const auto &[xi, yi] = points[i];
                    const auto &[xj, yj] = points[j];
                    return yi - xi == yj - xj ? xi < xj : yi - xi < yj - xj;
                }
            );

            std::vector<T> comp_x(n);
            for (int i = 0; i < n; ++i) comp_x[i] = points[i].first;
            std::sort(comp_x.begin(), comp_x.end());
            comp_x.erase(std::unique(comp_x.begin(), comp_x.end()), comp_x.end());
            const int m = comp_x.size();

            auto compress = [&](const T& x) { return std::lower_bound(comp_x.begin(), comp_x.end(), x) - comp_x.begin(); };

            PrefixMaxQuery<T> pmq(m);

            for (int i : p) {
                const auto& [x, y] = points[i];
                const int cx = compress(x);
                if (const auto v = pmq.prefix_query(cx + 1); v != e<T>()) {
                    res[i] = std::min(res[i], x + y - v);
                }
                pmq.apply(cx, x + y);
            }
        };

        for (int x_rev = 0; x_rev < 2; ++x_rev) {
            for (int y_rev = 0; y_rev < 2; ++y_rev) {
                for (int xy_rev = 0; xy_rev < 2; ++xy_rev) {
                    sweep();
                    for (auto& [x, y] : points) std::swap(x, y);
                }
                for (auto& [x, _] : points) x = -x;
            }
            for (auto& [_, y] : points) y = -y;
        }

        return res;
    }
} // namespace suisen


#endif // SUISEN_MANHATTAN_MINIMUM_DISTANCES

#line 1 "library/graph/manhattan_minimum_distances.hpp"



#include <algorithm>
#include <limits>
#include <numeric>
#include <vector>

#line 1 "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp"



#line 5 "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp"

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)()>
    struct FenwickTreePrefix {
        FenwickTreePrefix() : FenwickTreePrefix(0) {}
        explicit FenwickTreePrefix(int n) : _n(n), _dat(_n + 1, e()) {}
        FenwickTreePrefix(const std::vector<T> &dat) : _n(dat.size()), _dat(_n + 1, e()) {
            for (int i = _n; i > 0; --i) {
                _dat[i] = op(_dat[i], dat[i - 1]);
                if (int p = i + (-i & i); p <= _n) _dat[p] = op(_dat[p], _dat[i]);
            }
        }
        void apply(int i, const T& val) {
            for (++i; i <= _n; i += -i & i) _dat[i] = op(_dat[i], val);
        }
        T prefix_query(int r) const {
            T res = e();
            for (; r; r -= -r & r) res = op(res, _dat[r]);
            return res;
        }
    private:
        int _n;
        std::vector<T> _dat;
    };
} // namespace suisen



#line 10 "library/graph/manhattan_minimum_distances.hpp"

namespace suisen {
    namespace internal::manhattan_minimum_distances {
        template <typename T>
        T op(T x, T y) { return std::max(x, y); };
        template <typename T>
        T e() { return std::numeric_limits<T>::min(); };
        template <typename T>
        using PrefixMaxQuery = FenwickTreePrefix<T, op<T>, e<T>>;
    } // namespace internal::manhattan_minimum_distances

    template <typename T>
    std::vector<T> manhattan_minimum_distances(std::vector<std::pair<T, T>> points) {
        using namespace internal::manhattan_minimum_distances;

        const int n = points.size();
        std::vector<int> p(n);
        std::iota(p.begin(), p.end(), 0);

        std::vector<T> res(n, std::numeric_limits<T>::max());

        auto sweep = [&] {
            std::sort(
                p.begin(), p.end(),
                [&points](int i, int j) {
                    const auto &[xi, yi] = points[i];
                    const auto &[xj, yj] = points[j];
                    return yi - xi == yj - xj ? xi < xj : yi - xi < yj - xj;
                }
            );

            std::vector<T> comp_x(n);
            for (int i = 0; i < n; ++i) comp_x[i] = points[i].first;
            std::sort(comp_x.begin(), comp_x.end());
            comp_x.erase(std::unique(comp_x.begin(), comp_x.end()), comp_x.end());
            const int m = comp_x.size();

            auto compress = [&](const T& x) { return std::lower_bound(comp_x.begin(), comp_x.end(), x) - comp_x.begin(); };

            PrefixMaxQuery<T> pmq(m);

            for (int i : p) {
                const auto& [x, y] = points[i];
                const int cx = compress(x);
                if (const auto v = pmq.prefix_query(cx + 1); v != e<T>()) {
                    res[i] = std::min(res[i], x + y - v);
                }
                pmq.apply(cx, x + y);
            }
        };

        for (int x_rev = 0; x_rev < 2; ++x_rev) {
            for (int y_rev = 0; y_rev < 2; ++y_rev) {
                for (int xy_rev = 0; xy_rev < 2; ++xy_rev) {
                    sweep();
                    for (auto& [x, y] : points) std::swap(x, y);
                }
                for (auto& [x, _] : points) x = -x;
            }
            for (auto& [_, y] : points) y = -y;
        }

        return res;
    }
} // namespace suisen

Back to top page