提出 #29417326

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void chmin(int& a, int b){ if(a > b) a = b; }
void chmax(int& a, int b){ if(a < b) a = b; }


using T = array<int, 3>;
struct kDTree{
    using Iter = vector<T>::iterator;
    kDTree *l = nullptr, *r = nullptr;
    // 円形クエリのために x / y 座標の最小値と最大値を持つ
    int xmin = INT_MAX, xmax = INT_MIN, ymin = INT_MAX, ymax = INT_MIN;
    // 1 要素しか持っていない時の index
    int idx = -1;
    kDTree(Iter begin, Iter end){
        // vecqtor<T> で渡してもいいですが、コピーコストがかかるので in-place に
        for(auto p = begin; p != end; p++){
            auto [x, y, i] = *p;
            chmin(xmin, x);
            chmax(xmax, x);
            chmin(ymin, y);
            chmax(ymax, y);
        }
        const int size = int(end - begin);
        if(size == 1) idx = (*begin)[2];
        if(size <= 1) return;
        // 葉木なので x / y 座標で半分に分けて再帰
        auto cen = begin + size / 2;
        if(unsigned(xmax - xmin) > unsigned(ymax - ymin)){
            // 長い方で分ける (正方形に近い方が効率がいい)
            nth_element(begin, cen, end, [](T& a, T& b){ return a[0] < b[0]; });
        }
        else{
            nth_element(begin, cen, end, [](T& a, T& b){ return a[1] < b[1]; });
        }
        l = new kDTree(begin, cen);
        r = new kDTree(cen, end);
    }
    
    // sqrt(dx^2 + dy^2) ≤ K
    static bool inside(int dx, int dy, int K){
        return ll(dx) * dx + ll(dy) * dy <= ll(K) * K;
    }
    
    // (x, y) から距離 K 以下の点を f に報告する
    template<class F> void get(int x, int y, int K, F f) const {
        // [xmin, xmax] * [ymin, ymax] と ((x, y) から半径 K 以内) に共通部分がない
        if(!inside(clamp(x, xmin, xmax) - x, clamp(y, ymin, ymax) - y, K)) return;
        // 葉なら idx を報告
        if(idx != -1){
            f(idx);
            return;
        }
        l->get(x, y, K, f);
        r->get(x, y, K, f);
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    vector<T> A(N);
    for(auto& [x, y, i] : A) cin >> x >> y;
    for(int i = 0; i < N; i++) A[i][2] = i;
    vector<pair<int, int>> ans;
    kDTree tree(A.begin(), A.end());
    for(auto [x, y, i] : A) tree.get(x, y, K, [&, i = i](int j){ if(i < j) ans.emplace_back(i + 1, j + 1); });
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(auto [x, y] : ans) cout << x << ' ' << y << '\n';
}

提出情報

ジャッジ結果