Description：

给你 $n$ 个点，要你求一个整点，使得该点到所有给定的点的切比雪夫距离最小。

$1\le n \le 100000$

Solution：

先把切比雪夫距离转化成曼哈顿距离，则最后的答案为 $\begin{align}\sum_{i=1}^n|x-x_i'|+|y-y_i'|\end{align}$ 。

可以把横纵坐标分开来考虑，那么问题就变成了 $\begin{align}\sum_{i=1}^n|x-x_i'|+\sum_{i=1}^n|y-y_i'|\end{align}$ ，在一维上，就变成了一个中位数最优问题，但是有一个问题，就是找到的两个数不一定在原坐标系下是整点，由 $(x',y')=(\frac {x+y}2,\frac{x-y}2)$ 发现只有 $x$ 与 $y$ 奇偶性相同时才是整点，而如果这个点不是整点，那他在曼哈顿距离坐标系下上下左右四个点在原坐标系下是整点，枚举一下判断即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct point

{

	int x,y;

}p[MAXN];

int x[MAXN],y[MAXN];

int mx[4] = {0,0,1,-1};

int my[4] = {1,-1,0,0};

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d%d",&p[i].x,&p[i].y);

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

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

	}

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

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

	int nx = x[(n + 1) >> 1],ny = y[(n + 1) >> 1];

	if(((nx ^ ny) & 1) == 0)

	{

		long long ans = 0;

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

		{

			ans += abs(nx - p[i].x) + abs(ny - p[i].y);

		}

		cout << ans / 2 << endl;

		return 0;

	}

	long long ans = 0x3f3f3f3f3f3f3f3f;

	for(int k = 0;k < 4;++k)

	{

		int sx = nx + mx[k],sy = ny + my[k];

		long long res = 0;

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

		{

			res += abs(sx - p[i].x) + abs(sy - p[i].y);

		}

		ans = min(ans,res);

	}

	cout << ans / 2 << endl;

	return 0;

}