题目链接
正经解法：
给定n个点的坐标，找一个点，到其他点的曼哈顿距离之和最小。
n可以是100000。
大概要一个O（nlogn）的算法。
算曼哈顿距离可以把x和y分开计算排好序后计算前缀和就可以在O（1）时间内判断一个点到其他点的距离。
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100005
int t,n;
ll ans,sum[N],sx[N],sy[N];
struct p
{
int i;
ll x,y;
} a[N];
int cmpx(p a,p b)
{
return a.x<b.x;
}
int cmpy(p a,p b)
{
return a.y<b.y;
}
int main()
{
scanf("%d",&t);
while(t--)
{
sx[]=sy[]=;
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%lld%lld",&a[i].x,&a[i].y);
a[i].i=i;
}
sort(a+,a+n+,cmpx);
for(int i=; i<=n; i++)
sx[i]=sx[i-]+a[i].x;
for(int i=;i<=n;i++)
sum[a[i].i]=a[i].x*(i-)-sx[i-]+sx[n]-sx[i]-a[i].x*(n-i);
sort(a+,a+n+,cmpy);
for(int i=; i<=n; i++)
sy[i]=sy[i-]+a[i].y;
for(int i=; i<=n; i++)
{
sum[a[i].i]+=a[i].y*(i-)-sy[i-]+sy[n]-sy[i]-a[i].y*(n-i);
ans=(i==)?sum[a[].i]:min(ans,sum[a[i].i]);
}
printf("%lld\n",ans);
}
}
缩小范围法：
另外一种做法，当时我就是这么想的，但是后来没敢交，觉得还是会wa。
因为本身就不是很可靠。
按x排序后，取中间x的附近点来计算(经过我多次提交，发现这个范围不能小于±220，这就是难点所在了，为什么是250左右，赛场上全凭直觉取值)。
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
struct p{ll x,y;}a[];
ll ABS(ll a){
if(a<)a=-a;
return a;
}
ll dis(p a, p b){
return ABS(a.x-b.x)+ABS(a.y-b.y);
}
int cmp(p a,p b){
return a.x<b.x;
}
int main(){
int t,n,s,e;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lld%lld",&a[i].x,&a[i].y);
sort(a+,a++n,cmp);
s=n/-;
e=n/+;
if(s<)s=;
if(e>n)e=n;
ll ans=1LL<<;
for(int z=s;z<=e;z++){
ll s=;
for(int i=;i<=n;i++)
s+=dis(a[z],a[i]);
ans=min(s,ans);
}
printf("%lld\n",ans);
}
}