贪心、二分、线段树

对于二维问题有枚举一维，数据结构维护一维的套路；对于最大化最小值问题有二分答案的套路。

考虑枚举 $x$ 分割线的同时找到最优的 $y$ 分割线，这个做法似乎没有出路。

那么考虑二分答案，难点在于如何检查，考虑给定值 $mid$ 是否能成为答案。

枚举 $x$ 分割线将 $y$ 坐标划分为两个集合，对于一个集合求出最后一个合法 $y$ 分割线 $r$ 的值。具体地，设集合包含的点数为 $k$，如果 $k < mid$ 则必定不存在合法区间。

否则，找到满足集合中 $y$ 轴坐标大于等于 $Y$ 的点的数量不小于 $mid$ 的最大的整数 $Y$ 并记为 $r$，如果 $r$ 左边的点数同样不小于 $mid$ 则 $Y$ 是最小的合法分割线。在另一个集合中检查 $y$ 是否合法，如果合法那么 $mid$ 可以成为答案。因为若两个集合的合法 $y$ 分割线取值范围对应的区间有交，交集必定能取到其中一个区间的右界。

使用两棵线段树维护 $y$ 坐标对应的集合，线段树上二分求出合法分割线右界，离散化处理值域。

时间复杂度 $O(n \log ^2 n)$。

#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{
    struct Segment{int l,r,w;}s[800'005];
    void build(int u,int l,int r){
        s[u].l=l,s[u].r=r,s[u].w=0;
        if(l==r) return;
        build(u*2,l,(l+r)/2);
        build(u*2+1,(l+r)/2+1,r);
    }
    void update(int u,int p,int k){
        if(s[u].l==s[u].r) return s[u].w+=k,void();
        if(p<=s[u*2].r) update(u*2,p,k);
        else update(u*2+1,p,k);
        s[u].w=s[u*2].w+s[u*2+1].w;
    }
    int query(int u,int l,int r){
        if(s[u].l>r||s[u].r<l) return 0;
        if(s[u].l>=l&&s[u].r<=r) return s[u].w;
        return query(u*2,l,r)+query(u*2+1,l,r);
    }
    int rfrank(int u,int k){
        if(s[u].l==s[u].r) return s[u].l;
        if(k<=s[u*2+1].w) return rfrank(u*2+1,k);
        return rfrank(u*2,k-s[u*2+1].w);
    }
}seg[2];
int n,ax,ay,cnt,p[200'005];
pair<int,int> a[100'005];
bool fail(int x){
    seg[0].build(1,1,cnt),seg[1].build(1,1,cnt);
    for(int i=1;i<=n;i++) seg[1].update(1,a[i].second,1);
    int pos=n;
    for(int i=cnt;i>=1;i--){
        while(pos>=1&&a[pos].first>=i){
            seg[0].update(1,a[pos].second,1);
            seg[1].update(1,a[pos].second,-1);
            --pos;
        }
        if(min(seg[0].s[1].w,seg[1].s[1].w)<x) continue;
        for(int j=0;j<=1;j++){
            int r=seg[j].rfrank(1,x);
            if(seg[j].s[1].w-seg[j].query(1,r,cnt)<x) continue;
            int res=seg[j^1].query(1,r,cnt);
            if(min(res,seg[j^1].s[1].w-res)<x) continue;
            ax=p[i],ay=p[r];
            return 0;
        }
    }
    return 1;
}
void solution(){
    cin>>n,ax=0,ay=0,cnt=0;
    for(int i=1;i<=n;i++){
        auto &[x,y]=a[i];
        cin>>x>>y;
        p[++cnt]=x,p[++cnt]=y;
    }
    sort(p+1,p+cnt+1);
    cnt=unique(p+1,p+cnt+1)-p-1;
    for(int i=1;i<=n;i++){
        auto &[x,y]=a[i];
        x=lower_bound(p+1,p+cnt+1,x)-p;
        y=lower_bound(p+1,p+cnt+1,y)-p;
    }
    sort(a+1,a+n+1);
    int l=0,r=n/4,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(fail(mid)) r=mid-1;
        else ans=mid,l=mid+1;
    }
    fail(ans);
    cout<<ans<<'\n'<<ax<<' '<<ay<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}