1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int amn=1e5+5;
 5 struct node{
 6     ll x,y;
 7 }a[amn];
 8 multiset<ll> s;
 9 multiset<ll>::iterator it;
10 bool cmp(node a,node b){
11     if(a.x==b.x)return a.y>b.y;
12     return a.x>b.x;
13 }
14 int main(){
15     int n,T;
16     bool f;
17     ll ans,maxn;
18     scanf("%d",&T);
19     while(T--){
20         scanf("%d",&n);
21         for(int i=1;i<=n;i++){
22             scanf("%lld%lld",&a[i].x,&a[i].y);
23             s.insert(a[i].y);       ///将y值插入multiset
24         }
25         sort(a+1,a+1+n,cmp);    ///对学生按x降序排序
26         ans=1e18;
27         maxn=0;             ///maxn维护一个必须要加入y集合的学生中y值最大的值
28         for(int i=1;i<=n;i++){
29             s.erase(s.find(a[i].y));        ///因为现在把当前学生分到x集合中，所以删除当前学生在multiset中的y值
30             if(i>1)ans=min(ans,abs(a[i].x-maxn));    ///这里是关键，maxn代表必定要分到另一个集合的元素的最大值，而第一次没有必须要分到另一个集合中的元素，所以第一次是不能调用的，否则因为一开始maxn为0，所以第一次会将ans更新为a[1].x
31             it=s.lower_bound(a[i].x);       ///在multiset中二分一个和当前学生x值最接近的值
32             if(it!=s.begin()&&it==s.end())it--;     ///lower_bound会返回第一个大于等于搜索值的地址，如果不存在则返回s.end(),所以如果迭代器不是s.begin()且是s.end()则要将其指向上一个元素
33             if(*it>=maxn)ans=min(ans,abs(a[i].x-*it));  ///因为一个集合的代表值是这个集合中所以元素中的最大值，所以二分到的值必须要大于maxn才能更新ans
34             if(it!=s.begin()){          ///如果前面还有元素，则看上一个元素是否符合条件
35                 it--;
36                 if(*it>=maxn)ans=min(ans,abs(a[i].x-*it));
37             }
38             maxn=max(maxn,a[i].y);      ///现在这个学生必须要被加到y集合中了，更新一下maxn
39         }
40         printf("%lld\n",ans);
41     }
42 }
43 /**
44 有n个学生，每个学生有x值和y值，每个学生必须要么进入x集合要么y集合，x集合的代表值是这个集合中最大的x值，y集合同理，问如何分配学生才能使得x集合代表值与y集合的代表值差值最小
45 n最大1e5，所以复杂度最大只能为O(nlogn),可以考虑遍历x集合的同时二分y集合
46 用一个结构体存学生的x值和y值，并对对学生按x和y降序排序，将学生的y值加入到multiset中
47 因为现在是降序排序，所以如果选了一个学生代表x集合的代表，则x比他大的学生都必须要加入到y集合中，而比小于等于他的那些则可以随意
48 所以我们枚举每个学生当x集合的代表，并将其在y集合中的值删掉，用maxn维护必须要加入y集合的那些值的最大值，multiset维护可能可以加入y集合的值，并multiset中二分一个和他最接近的值（可能大于，等于或小于，所以如果it!=s.end()还有it--判断)，
49 当然这个值要比()才能更新ans，再用maxn和现在这个学生x值的差值更新ans,这个学生判断完后就去判断下一个学生，当然因为我们对他们x值降序排序了，所以这个学生就必须加入y集合，用其y值更新maxn
50 注意(坑点):
51 1.maxn代表必定要分到另一个集合的元素，而第一次没有必须要分到另一个集合中的元素，所以第一次是不能调用的
52 2.因为一个集合的代表值是这个集合中所以元素中的最大值，所以二分到的值必须要大于maxn才能更新ans
53 **/