Description：

给 $n$ 个点，选一个点使得这个点到其他所有点的切比雪夫距离之和最小。

$1\le n \le 100000$

Solution：

首先把切比雪夫距离转化成曼哈顿距离 $(x,y)\to (\frac {x+y}2,\frac{x-y}2)$ ，这样在原坐标系下的切比雪夫距离就是新坐标系下的曼哈顿距离，然后答案就是 $\begin{align}\sum_{i=1}^n|x_i'-x|+|y_i'-y|\end{align}$ ，然后我们把 $x$ 和 $y$ 分别来看，就变成了 $\begin{align}\sum_{i=1}^n|x_i'-x|+\sum_{i=1}^n|y'_i-y|\end{align}$ ，然后依次枚举每个点在 $x$ 和 $y$ 序列中二分他的位置，用前缀和求距离就行了。

$double$ 会掉精度（掉成爆零），所以最后再除二。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

typedef long long ll;

struct point

{

	ll x,y;

}p[MAXN],s[MAXN];

ll x[MAXN],y[MAXN];

ll sumx[MAXN],sumy[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lld%lld",&p[i].x,&p[i].y);

	for(int i = 1;i <= n;++i)

	{

		s[i].x = x[i] = p[i].x + p[i].y;

		s[i].y = y[i] = p[i].x - p[i].y;

	}

	sort(x + 1,x + 1 + n);

	for(int i = 1;i <= n;++i)sumx[i] = sumx[i - 1] + x[i];

	sort(y + 1,y + 1 + n);

	for(int i = 1;i <= n;++i)sumy[i] = sumy[i - 1] + y[i];

	ll ans = 0x3f3f3f3f3f3f3f3f;

	int p;

	for(int i = 1;i <= n;++i)

	{

		ll res = 0;

		p = lower_bound(x + 1,x + 1 + n,s[i].x) - x;

		res += p * s[i].x - sumx[p] + sumx[n] - sumx[p] - (n - p) * s[i].x;

		p = lower_bound(y + 1,y + 1 + n,s[i].y) - y;

		res += p * s[i].y - sumy[p] + sumy[n] - sumy[p] - (n - p) * s[i].y;

		ans = min(ans,res);

	}

	cout << ans / 2 << endl;

	return 0;

}