点击查看代码
#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;
int n,D;
struct Node{int x,y;bool operator<(const Node& t) const {return x<t.x;}
}a[N];
deque<int> q1,q2;int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>D;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}sort(a+1,a+n+1);int l=0,r=0;int ans=2e9;for(r=1;r<=n;r++){while(!q1.empty()&&a[r].y>=a[q1.back()].y) q1.pop_back();q1.push_back(r);while(!q2.empty()&&a[r].y<=a[q2.back()].y) q2.pop_back();q2.push_back(r);while(a[q1.front()].y-a[q2.front()].y>=D){ans=min(ans,a[r].x-a[l].x);if(q1.front()==l) q1.pop_front();if(q2.front()==l) q2.pop_front();l++;}}if(ans==2e9){cout<<"-1"<<endl;}else{cout<<ans<<endl;}return 0;
}