看心情填坑

http://poj.org/problem?id=3212

题意不好看懂，其实就是平面上有若干个点，定义两点距离为max(abs(x[i]-x[j]),abs(y[i]-y[j])),让你求一个点，使得它到其他点的距离之和尽可能小，n<=10W。

和BZOJ3210唯一不同的一点就是只能取给出的点，所以算出两维各自对每个点的距离的贡献直接上就行啦。

一种是在算式层面上的理解，即max(abs(x[i]-x[j]),abs(y[i]-y[j]))=abs(x[i]+y[i]-x[j]-y[j])+abs(x[i]-y[i]-x[j]+y[j])

另外一种是在坐标系上的理解，即将坐标系旋转45^。之后做，两种做法本质是一样的。

#include<cstdio>
#include<algorithm>
using namespace std;
struct el{
	int a,b,k;
}e[100005];
int x,y,n;
long long now,ans[100005];
bool cmp1(el k1,el k2){return k1.a<k2.a;}
bool cmp2(el k1,el k2){return k1.b<k2.b;}
long long Min(long long k1,long long k2){return k1>k2?k2:k1;}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		e[i].a=x+y;
		e[i].b=x-y;
		e[i].k=i;
	}
	sort(e+1,e+1+n,cmp1);
	now=0;
	for(int i=2;i<=n;i++)now+=e[i].a-e[1].a;
	ans[e[1].k]+=now;
	for(int i=2;i<=n;i++){
		now+=1LL*(i-1)*(e[i].a-e[i-1].a);
		now-=1LL*(n-i+1)*(e[i].a-e[i-1].a);
		ans[e[i].k]+=now;
	}
	sort(e+1,e+1+n,cmp2);
	now=0;
	for(int i=2;i<=n;i++)now+=e[i].b-e[1].b;
	ans[e[1].k]+=now;
	for(int i=2;i<=n;i++){
		now+=1LL*(i-1)*(e[i].b-e[i-1].b);
		now-=1LL*(n-i+1)*(e[i].b-e[i-1].b);
		ans[e[i].k]+=now;
	}
	long long Ans=2000000000000000;
	for(int i=1;i<=n;i++)Ans=Min(Ans,ans[i]);
	printf("%lld\n",Ans/2);
}

PS：写这题主要是因为第一种理解可以推广到n维平面上，但第二种理解推广到n维平面上就不好做了，可以在一些max,min问题上有很好的效果，具体例子POJ3244