一年前模拟赛的题，时隔恰好一年零一天又考了一遍还是不会做。
对两个矩形的位置分情况：
-
相离，此时必然存在一条与 \(x\) 轴或 \(y\) 轴平行的分界线，满足一个矩形在左边（下面），另一个矩形在右边（上面）。这部分显然可以 \(O(n)\) 地处理。
-
相交成十字形。这一类我的处理比较烦：考虑预处理 \(mnl_i,mxl_i,mnr_i,mxr_i\) 分别表示横坐标 \(\le i\) 中的点纵坐标的最小值、横坐标 \(\le i\) 中的点纵坐标的最大值、横坐标 \(\ge i\) 中的点纵坐标的最小值、横坐标 \(\ge i\) 中的点纵坐标的最大值。那么答案等价于 \(\min\limits_{l\le r}\{(r-l)·(maxy-miny)+(\max(mxl_{l-1},mxr_{r+1})-\min(mnl_{l-1},mnr_{r+1}))·(maxx-minx)\}\)，然后我分治，处理 \(L\le l\le mid,mid+1\le r\le R\) 的 \((l,r)\) 的贡献，这样左边若干个二元组 \((mnl_{l-1},mxl_{l-1})\)，右边若干个二元组 \((mnr_{r+1},mxr_{r+1})\)，每个二元组还有个权值，然后你要从左右各选一个二元组出来，选二元组 \((l_1,r_1,w_1),(l_2,r_2,w_2)\) 会产生 \(w_1+w_2+V·(\max(r_1,r_2)-\min(l_1,l_2))\) 的贡献，其中 \(V\) 是定值，这显然可以用类似于“按第一维排序，然后用树状数组处理第二维的偏序关系”的做法维护，时间复杂度 \(O(n\log^2n)\)。
-
相交成八字形，即两个矩形各覆盖一个角。这里假设是左下和右上（注：这里按照笛卡尔坐标系里的定义来，即左下方向是 \(x\) 变小，\(y\) 变小的方向），另一部分情况你把所有 \(y_i\) 都变成 \(maxy+miny-y_i\) 再做一遍即可。那么答案相当于 \(\min\limits_{xl\le xr,yl\le yr\\yr\ge mxl_{xl-1}\\yl\le mnr_{xr+1}}(maxx-xl)(maxy-yl)+(xr-minx)(yr-minx)\)。这个式子看起来很鬼畜，而且仔细思考你会发现要凸包什么的，并且这里面一坨限制也不太好处理，这样复杂度很可能是 3log 甚至 4log 的，不好。发掘些性质：你发现你选择的 \(xl\) 肯定得是 \(y\) 坐标的前缀最大值。因为如果不是前缀最大值你把它调整到它下一个 \(y\) 比它大的位置肯定更优，\(xr\) 则是后缀最小值，这样你可以写出如下的暴力代码：
namespace Part3{ pii pre[MAXN+5],suf[MAXN+5];int lp,ls; void work(){ lp=ls=0; for(int i=1;i<=n;i++){ if(!lp||(x[ordx[i]]!=pre[lp].fi&&y[ordx[i]]>pre[lp].se)) pre[++lp]=mp(x[ordx[i]],y[ordx[i]]); else if(lp&&x[ordx[i]]==pre[lp].fi)chkmax(pre[lp].se,y[ordx[i]]); } for(int i=n;i;i--){ if(!ls||(x[ordx[i]]!=suf[ls].fi&&y[ordx[i]]<suf[ls].se)) suf[++ls]=mp(x[ordx[i]],y[ordx[i]]); else if(ls&&x[ordx[i]]==suf[ls].fi)chkmin(suf[ls].se,y[ordx[i]]); } for(int i=2;i<=lp;i++)for(int j=2;j<=ls;j++){ pii pl=mp(pre[i].fi,suf[j-1].se),pr=mp(suf[j].fi,pre[i-1].se); if(pl.fi<=pr.fi&&pl.se<=pr.se) chkmin(res,1ll*(mxx-pl.fi)*(mxy-pl.se)+1ll*(pr.fi-mnx)*(pr.se-mny)); } } void solve(){ work(); for(int i=1;i<=n;i++)y[i]=mxy+mny-y[i]; work(); } }考虑优化，在上面的代码里，注意对于一个固定的 \(i\)，符合那个
if的 \(j\) 实际上是一段区间，这是由我们单调栈的性质可以直接得出来的，因此先二分找到这段区间。这样转化个模型：有 \(k_1\) 个二元组 \((x1_i,y1_i)\) 和 \(k_2\) 个二元组 \((x2_i,y2_i)\)，你要求 \(\min\limits_{1\le i\le k_1}\min\limits_{l_i\le j\le r_i}\{x1_ix2_j+y1_iy2_j\}\)。这是经典的凸包模型，变形为 \(x1_i(x2_j+y2_j·\dfrac{x2_i}{x1_i})\)，这样看作有若干个形如 \((-y2_j,x2_j)\) 的点，用斜率为 \(\dfrac{x2_i}{x1_i}\) 直线去切凸包，求最小截距。线段树维护凸包即可。
非常难写。时间复杂度 \(O(n\log^2n)\)。
const int MAXN=1e5;
const int INF=0x3f3f3f3f;
int n,x[MAXN+5],y[MAXN+5],ordx[MAXN+5],ordy[MAXN+5];ll res;
int mnx,mxx,mny,mxy;
namespace Part1{
void solve(){
multiset<int>xl,xr,yl,yr;
for(int i=1;i<=n;i++)xr.insert(x[i]),yr.insert(y[i]);
for(int i=1;i<n;i++){
xr.erase(xr.find(x[ordx[i]]));yr.erase(yr.find(y[ordx[i]]));
xl.insert(x[ordx[i]]);yl.insert(y[ordx[i]]);
chkmin(res,1ll*((*xl.rbegin())-(*xl.begin()))*((*yl.rbegin())-(*yl.begin()))+
1ll*((*xr.rbegin())-(*xr.begin()))*((*yr.rbegin())-(*yr.begin())));
}
xl.clear();xr.clear();yl.clear();yr.clear();
for(int i=1;i<=n;i++)xr.insert(x[i]),yr.insert(y[i]);
for(int i=1;i<n;i++){
xr.erase(xr.find(x[ordy[i]]));yr.erase(yr.find(y[ordy[i]]));
xl.insert(x[ordy[i]]);yl.insert(y[ordy[i]]);
chkmin(res,1ll*((*xl.rbegin())-(*xl.begin()))*((*yl.rbegin())-(*yl.begin()))+
1ll*((*xr.rbegin())-(*xr.begin()))*((*yr.rbegin())-(*yr.begin())));
}
}
}
namespace Part2{
int pmx[MAXN+5],pmn[MAXN+5],smx[MAXN+5],smn[MAXN+5];
void solve(){
pmx[0]=smx[n+1]=0;pmn[0]=smn[n+1]=INF;
for(int i=1;i<=n;i++)pmx[i]=max(pmx[i-1],y[ordx[i]]),pmn[i]=min(pmn[i-1],y[ordx[i]]);
for(int i=n;i;i--)smx[i]=max(smx[i+1],y[ordx[i]]),smn[i]=min(smn[i+1],y[ordx[i]]);
for(int i=2;i<n;i++)for(int j=i+1;j<n;j++)
chkmin(res,1ll*(x[ordx[j]]-x[ordx[i]])*(mxy-mny)+1ll*(max(pmx[i-1],smx[j+1])-min(pmn[i-1],smn[j+1]))*(mxx-mnx));
}
}
namespace Part3{
pii pre[MAXN+5],suf[MAXN+5];int lp,ls;
void work(){
lp=ls=0;
for(int i=1;i<=n;i++){
if(!lp||(x[ordx[i]]!=pre[lp].fi&&y[ordx[i]]>pre[lp].se))
pre[++lp]=mp(x[ordx[i]],y[ordx[i]]);
else if(lp&&x[ordx[i]]==pre[lp].fi)chkmax(pre[lp].se,y[ordx[i]]);
}
for(int i=n;i;i--){
if(!ls||(x[ordx[i]]!=suf[ls].fi&&y[ordx[i]]<suf[ls].se))
suf[++ls]=mp(x[ordx[i]],y[ordx[i]]);
else if(ls&&x[ordx[i]]==suf[ls].fi)chkmin(suf[ls].se,y[ordx[i]]);
}
for(int i=2;i<=lp;i++)for(int j=2;j<=ls;j++){
pii pl=mp(pre[i].fi,suf[j-1].se),pr=mp(suf[j].fi,pre[i-1].se);
if(pl.fi<=pr.fi&&pl.se<=pr.se)
chkmin(res,1ll*(mxx-pl.fi)*(mxy-pl.se)+1ll*(pr.fi-mnx)*(pr.se-mny));
}
}
void solve(){
work();
for(int i=1;i<=n;i++)y[i]=mxy+mny-y[i];
work();
}
}
void solve(){
scanf("%d",&n);res=2e18;
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
if(n==1)return puts("0"),void();
for(int i=1;i<=n;i++)ordx[i]=ordy[i]=i;
sort(ordx+1,ordx+n+1,[&](int p,int q){return x[p]<x[q];});
sort(ordy+1,ordy+n+1,[&](int p,int q){return y[p]<y[q];});
mnx=x[ordx[1]];mxx=x[ordx[n]];mny=y[ordy[1]];mxy=y[ordy[n]];
Part1::solve();Part2::solve();Part3::solve();
printf("%lld\n",res);
}
int main(){
int qu;scanf("%d",&qu);
while(qu--)solve();
return 0;
}