文件详细信息

下载本文件

本文件的大小为 1245 字节。

#include<algorithm>
#include<cstdio>
namespace IO{
	const int ARR_SIZE=1<<24;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),*(IO::si++))
	char input[ARR_SIZE],*si=input,*ti=input;
	template<typename T>
	void read(T&num){
		bool flag=true;
		int ch=gc();
		num=0;
		while(ch<48||ch>57){
			if(ch=='-')flag=false;
			ch=gc();
		}
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
		flag||(num=-num);
	}
}
using IO::read;
template<typename T>
T min(T a,T b){
	return a<b?a:b;
}
typedef long long ll;
const int maxn=100005;
int n,x[maxn],y[maxn];
ll sumx[maxn],sumy[maxn];
struct Input{
	int x,y;
}a[maxn];
int main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i].x),read(a[i].y);
		x[i]=a[i].x+a[i].y,y[i]=a[i].x-a[i].y;
		a[i].x=x[i],a[i].y=y[i];
	}
	std::sort(x+1,x+n+1);
	for(int i=1;i<=n;i++)sumx[i]=sumx[i-1]+x[i];
	std::sort(y+1,y+n+1);
	for(int i=1;i<=n;i++)sumy[i]=sumy[i-1]+y[i];
	ll ans=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=n;i++){
		int rx=std::lower_bound(x+1,x+n+1,a[i].x)-x;
		int ry=std::lower_bound(y+1,y+n+1,a[i].y)-y;
		ans=min(ans,sumx[n]-(sumx[rx]<<1)+(ll)((rx<<1)-n)*a[i].x+sumy[n]-(sumy[ry]<<1)+(ll)((ry<<1)-n)*a[i].y);
	}
	printf("%lld\n",ans>>1);
	return 0;
}