把每个点分到 \((\left\lfloor\frac{x}{K}\right\rfloor, \left\lfloor\frac{y}{K}\right\rfloor)\) 的正方形内，枚举相邻正方形，计入答案。
正确性显然。
复杂度证明就是所有每个正方形内距离为 \(K\) 的点对下界为 \(\Omega(n^2)\)。考虑分成四个边长为 \(\frac{K}{2}\) 的小正方形，显然每个小正方形内的点对都满足条件。根据抽屉原理，设四个小正方形内点数分别为 \(a \ge b \ge c \ge d\)，则有 \(a \ge \frac{x}{4}\)，\(x\) 为大正方形内的点数。那么大正方形内合法点对的下界为 \(\frac{a(a-1)}{2}\)，这个是 \(O(n^2) = 4 \times 10^5\) 级别的。然后枚举相邻的正方形，均值不等式易得枚举的点对也是 \(O(n^2) = 4 \times 10^5\) 级别的。然后就做完了。
code
// Problem: Ex - Enumerate Pairs
// Contest: AtCoder - AtCoder Beginner Contest 234
// URL: https://atcoder.jp/contests/abc234/tasks/abc234_h
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, m;
pii a[maxn];
map< pii, vector<int> > mp;
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &a[i].fst, &a[i].scd);
mp[make_pair(a[i].fst / m, a[i].scd / m)].pb(i);
}
vector<pii> ans;
for (int i = 1; i <= n; ++i) {
for (int p = -1; p <= 1; ++p) {
for (int q = -1; q <= 1; ++q) {
for (int x : mp[make_pair(a[i].fst / m + p, a[i].scd / m + q)]) {
if (i < x && (a[i].fst - a[x].fst) * (a[i].fst - a[x].fst) + (a[i].scd - a[x].scd) * (a[i].scd - a[x].scd) <= m * m) {
ans.pb(i, x);
}
}
}
}
}
sort(ans.begin(), ans.end());
printf("%d\n", (int)ans.size());
for (pii p : ans) {
printf("%lld %lld\n", p.fst, p.scd);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}