记录编号	574943	评测结果	AAAAAAAAAA
题目名称	双倍腹肌量	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.491 s
提交时间	2022-08-30 00:04:12	内存使用	4.13 MiB

#include <bits/stdc++.h>
#define x first
#define y second

using PII = std::pair<int, int>;

bool cmp(PII a, PII b) { return a.x < b.x; }

const int N = 100010, T = 320;
int n, m, t, ans = 1e9;
int pos[N], L[T], R[T], M[T];
PII a[N];

int main() {
    freopen("double_muscle.in", "r", stdin); 
    freopen("double_muscle.out", "w", stdout);
    std::cin >> n >> m, t = std::sqrt(n);
    for (int i = 1; i <= n; ++ i) {
        int x, y; std::cin >> x >> y;
        a[i] = {x, y};
    }
    std::sort(a + 1, a + 1 + n, [](PII a, PII b) {
        return a.y < b.y;
    });
    for (int i = 1; i <= t; ++ i) 
        L[i] = (i - 1) * t + 1, R[i] = i * t,
        std::sort(a + L[i], a + R[i] + 1, cmp);
    if (R[t] < n) 
        L[t + 1] = R[t] + 1, R[++ t] = n,
        std::sort(a + L[t], a + R[t] + 1, cmp);
    for (int i = 1; i <= t; ++ i) 
        for (int j = L[i]; j <= R[i]; ++ j) 
            pos[j] = i,
            M[i] = (M[i] == 0) ? a[j].y : std::min(M[i], a[j].y);
    for (int i = 1; i <= n; ++ i) {
        int k = std::upper_bound(M + 1, M + 1 + t, a[i].y + m) - M;
        for (int j = k; j <= t; ++ j) {
            int x = std::upper_bound(a + L[j], a + R[j], a[i]) - a;
            int y = std::lower_bound(a + L[j], a + R[j], a[i]) - a;
            x = std::abs(a[x].x - a[i].x);
            y = std::abs(a[y].x - a[i].x);
            ans = std::min({ans, x, y});
        }
        for (int j = L[k - 1]; j <= R[k - 1]; ++ j)
            if (a[i].y + m < a[j].y)
                ans = std::min(ans, std::abs(a[i].x - a[j].x));
    }
    std::cout << ans << '\n';
    return 0;
}