题目链接
Solution
转化一下,就是个单调队列.
可以发现就是一段区间 \([L,R]\) 使得其高度的极差不小于 \(d\) ,同时满足 \(R-L\) 最小.
然后可以考虑二分然后再 \(O(n)\) 判断, 时间复杂度 \(O(nlogn)\) .
Code
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1000008;ll n,d;
ll ans;
struct point{ll x,y;
}a[maxn];
bool jud(int len)
{int qmax[maxn],qmin[maxn];int h1,h2,t1,t2;h1=h2=1,t1=t2=0;qmax[0]=qmin[0]=0;for(int i=1;i<=n;++i){while(h1<=t1 && a[i].y>a[qmax[t1]].y)--t1;qmax[++t1]=i;while(h2<=t2 && a[i].y< a[qmin[t2]].y)--t2;qmin[++t2]=i;while(h1<=t1 && a[i].x-a[qmax[h1]].x>len)++h1;while(h2<=t2 && a[i].x-a[qmin[h2]].x>len)++h2;if(a[qmax[h1]].y-a[qmin[h2]].y>=d) return 1;}return 0;
}bool cmp(point s,point t)
{return s.x<t.x;}int main()
{scanf("%lld%lld",&n,&d);for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);sort(a+1,a+n+1,cmp);int l=1,r=maxn;while(l<=r){int mid=(l+r)>>1;if(jud(mid)){ans=mid;r=mid-1;}else l=mid+1;}if(ans)printf("%lld\n",ans);else puts("-1\n");return 0;
}