题目大意:

有n对数字,让你将这n对数字染色成红的或蓝的,求\((Rmax-Rmin)*(Bmax-Bmin)\)
\(n<=2e5,0<a<=1e9\)

解题过程:

还是luogu比较香.....
在atcode上不会做今天用luogu看就会了是什么鬼...
(难道我的水平和OJ界面成正比???)
首先这里只有两组而且显然是计算答案的时候是对称的两组
所以考虑让最大值出现在R里面,那么最小值就有两种情况

  • 最小值出现在B里面
    那就很easy了,让\(Rmin\)最大,\(Bmax\)最小即可,直接
    大的丢到\(a\)里小的丢到\(b\)里就行
  • 最小值出现在\(R\)里面
    这个比较烦,但是手玩一下样例还是可以搞的
    我们现在是想让\(Bmax\)最小,\(Bmin\)最大就行
    那么就先满足\(Bmax\)最小这个条件,按每一组
    的最小值排序,先把小的丢给B,大的丢给R,然后
    从前到后枚举每一个数对,把它翻过去,然后更新答案就行
    那么为啥可以这样咧?
    因为我们从前到后翻的时候最小值在不断变
    大,如果我们把前面的一个翻回来,那么最小值就会变小,而最大值
    并不会变化,那么答案就变大了,舍弃。如果强行把最大值调小
    那么你会发现这种情况之前已经枚举过了,不用考虑
    综上所述,我们枚举一遍,同时维护最大最小值就可以了
    直接开线段树就行,\(2e5\)丝毫不慌的.
    (我去,线段树跑这么快????)
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

#define R register
#define ll long long

const ll inf=(1LL<<60);
const int MAXN=2e5+10;

int n;
struct Pair
{
	int x,y;
}p[MAXN];

ll ans=inf;
int a[MAXN],b[MAXN];

inline void solve1()
{
	for(R int i=1;i<=n;i++)
	a[i]=p[i].x,b[i]=p[i].y;
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	ll res=(ll)(a[n]-a[1])*(b[n]-b[1]);
	if(res<ans) ans=res;
}

struct Segment_Tree
{
	int mx[MAXN<<2],mn[MAXN<<2];
	inline int ls(int x) { return x<<1; }
	inline int rs(int x) { return x<<1|1; }
	inline void update(int x)
	{
		mx[x]=max(mx[ls(x)],mx[rs(x)]);
		mn[x]=min(mn[ls(x)],mn[rs(x)]);
	}
	inline void chg(int x,int l,int r,int ad,int k)
	{
		if(l==r)
		{
			mn[x]=mx[x]=k;
			return;
		}
		int mid=l+r;mid>>=1;
		if(ad<=mid) chg(ls(x),l,mid,ad,k);
		else chg(rs(x),mid+1,r,ad,k);
		update(x);
	}
	inline int findmin()
	{
		return mn[1];
	}
	inline int findmax()
	{
		return mx[1];
	}
}Tr,Tb;

inline bool cmp(Pair p1,Pair p2)
{
	if(p1.x==p2.x) return p1.y<p2.y;
	return p1.x<p2.x;
}

int tag[MAXN];

inline void solve2()
{
	sort(p+1,p+1+n,cmp);
	int mxnode=-1,mxnum1=-1,mxnum2=-1;
	for(R int i=1;i<=n;i++)
	{
		if(p[i].y>mxnum1)
		{
			mxnode=i;
			mxnum1=p[i].y;
			mxnum2=p[i].x;
			continue;
		}
		if(p[i].y==mxnum1)
		{
			if(p[i].x>mxnum2)
			{
				mxnode=i;
				mxnum2=p[i].x;
				continue;
			}
		}
	}
	tag[mxnode]=1;
	swap(p[1].x,p[1].y);
	tag[1]=1;
	for(R int i=1;i<=n;i++)
	{
		Tb.chg(1,1,n,i,p[i].x);
		Tr.chg(1,1,n,i,p[i].y);
	}
	ll res=(ll)(Tb.findmax()-Tb.findmin())*(Tr.findmax()-Tr.findmin());
	if(res<ans) ans=res;
	for(R int i=1;i<=n;i++)
	{
		if(tag[i]) continue;
		Tb.chg(1,1,n,i,p[i].y);
		Tr.chg(1,1,n,i,p[i].x);
		ll tres=(ll)(Tb.findmax()-Tb.findmin())*(Tr.findmax()-Tr.findmin());
		if(tres<ans) ans=tres;
	}
}

int main()
{
	scanf("%d",&n);
	for(R int i=1;i<=n;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		if(x>y) swap(x,y);
		p[i].x=x;
		p[i].y=y;
	}
	solve1();
	solve2();
	printf("%lld\n",ans);
	return 0;
}