这个提交（我校其他同学的代码，拿过来测，应该不算抄袭吧）的时间复杂度为 $O(n^2 \log n)$，但也通过了

https://www.luogu.com.cn/record/78397880：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long LL;
struct node
{
	int x,y;
} 
nd[1000005]={0};
bool cmp(node a,node b)
{
	if(a.y<=b.y)return true;
	else return false;
}
int arr[1000005]={0};
int mn=1e+10,t,n,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>nd[i].x>>nd[i].y;
	}
	sort(nd+1,nd+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		node tmp=nd[i];
		tmp.y+=m;
		int p=upper_bound(nd+i+1,nd+n+1,tmp,cmp)-nd;
		for(int j=p;j<=n;j++)
		{
			int dtc=abs(nd[j].x-tmp.x);
			mn=min(dtc,mn);
		}
	}
	if(mn>1000000)
	{
		cout<<-1;
		return 0;
	 } 
	cout<<mn;
	return 0;
}

$O(n \log n)$ 做法：

https://www.luogu.com.cn/record/78112813：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>

using namespace std;

const int N = 1e5 + 10;

int l = 0, r = 1e6, mid;
int n, d;

struct node{
	int x, y;
}a[N];

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

deque <int> qa;
deque <int> qi;

bool check(int w){
	qa.clear();
	qi.clear();
	for(int i = 0; i < n; i++){
		while(!qa.empty() && a[qa.back()].y < a[i].y){
			qa.pop_back();
		}
		while(!qi.empty() && a[qi.back()].y > a[i].y){
			qi.pop_back();
		}
		while(!qa.empty() && (a[i].x - a[qa.front()].x) > w){
			qa.pop_front();
		}
		while(!qi.empty() && (a[i].x - a[qi.front()].x) > w){
			qi.pop_front();
		}
		qa.push_back(i);
		qi.push_back(i);
		if(a[qa.front()].y - a[qi.front()].y >= d){
			return 1;
		}
	}
	return 0;
}

int main(){
	
	scanf("%d%d", &n, &d);
	
	for(int i = 0; i < n; i++){
		scanf("%d%d", &a[i].x, &a[i].y);
	}
	
	sort(a, a+n, cmp);
	
	while(l < r){
		mid = (l + r) / 2;
		if(check((mid))){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	
	if(l == 1e6){
		puts("-1");
	}else{
		printf("%d\n", l);
	}
	
	return 0;
}

学校同学写的：

代码中以下部分，时间复杂度为 $O(n^{2} \log n)$：

for(int i=1;i<=n;i++)
{
	node tmp=nd[i];
	tmp.y+=m;
	int p=upper_bound(nd+i+1,nd+n+1,tmp,cmp)-> nd;
	for(int j=p;j<=n;j++)
	{
		int dtc=abs(nd[j].x-tmp.x);
		mn=min(dtc,mn);
	}
}

至于为什么会出现这种情况，我们检查后发现，原题的数据范围规定了 $0 \leq x,\ y \le 10^{6}$，与 $1 \leq n \le 10^{5}$ 相差不大，所以按照纵坐标排序后，相邻两个点纵坐标相差并不大，在随机数据上平均只有 $10$，远远小于 $D$，所以 upper_bound(nd+i+1,nd+n+1,tmp,cmp) 找到的点会比 $i$ 大很多很多，甚至接近 $n$，以至于内层循环耗时很短。

知道了原理，hack 起来就比较简单了，构造数据使得 upper_bound(nd+i+1,nd+n+1,tmp,cmp) 每次均找到 $i + 1$，这可以让代码近似跑满 $O(n^{2} \log n)$。只需要构造排序后的相邻两个点纵坐标差大于 $D$ 即可。

python 构造 hack数据方法：

import os

with open("vase.in", "w") as f:
    f.write("100000 5\n")
    for i in range(100000):
        f.write("%d %d\n" % (i*10, i*10))
# 答案为 10

hack 数据：https://www.luogu.com.cn/paste/fvh5elvk

不知道 USACO 的原题添加 hack 合不合适，不合适的话联系我删除此贴。

---

前人也有发现别的问题，顺带挂个链接：https://www.luogu.com.cn/discuss/78241