1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
|
using namespace std; struct { long long f,s; }a[100100]; bool cmp1(node x,node y){ if (x.f==y.f) return x.s>y.s; return x.f>y.f; } long long m[100100]; int n; set <long long> q; set <long long>::iterator it1; map <long long,int> mp; int main(){ int T; scanf("%d",&T); while (T--){ scanf("%d",&n); for (int tt=1;tt<=n;tt++){ scanf("%lld%lld",&a[tt].f,&a[tt].s); mp[a[tt].s]++; q.insert(a[tt].s); } sort(a+1,a+1+n,cmp1); m[1]=a[1].s; m[0]=0; for (int i=2;i<=n;i++){ m[i]=max(m[i-1],a[i].s); } long long ans=1e18; for (int i=1;i<=n;i++){ mp[a[i].s]--; if (mp[a[i].s]==0) q.erase(a[i].s); long long maxx=a[i].f; it1=q.lower_bound(maxx); long long temp=m[i-1]; if(it1!=q.end()){ if(i!=1)ans=min(ans,abs(a[i].f-temp)); if((*it1)>=temp) ans=min(ans,abs(a[i].f-(*it1))); if(it1!=q.begin()&&(*(--it1)>temp)) { ans=min(ans,abs(a[i].f-(*it1))); } } else{ ans=min(ans,abs(a[i].f-temp)); if(*(--it1)>temp) ans=min(ans,abs(a[i].f-*it1)); } mp[a[i].s]++; q.insert(a[i].s); } printf("%lldn",ans); mp.clear(); q.clear(); } return 0; }
|
近期评论