BZOJ 3210: 花神的浇花集会 (切比雪夫距离)

GXZlegend

切比雪夫和曼哈顿距离的互相转化看这里 传送门

CODE

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int MAXN = 100005;
int n, a[MAXN], b[MAXN], x[MAXN], y[MAXN];
inline LL f(int px, int py) {
	LL re = 0;
	for(int i = 1; i <= n; ++i)
		re += abs(x[i]-px) + abs(y[i]-py);
	return re>>1;
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d%d", &a[i], &b[i]), x[i] = a[i]+b[i], y[i] = a[i]-b[i];
	sort(x + 1, x + n + 1);
	sort(y + 1, y + n + 1);
	int px = x[n+1>>1], py = y[n+1>>1];
	if((px^py)&1) printf("%lld
", min(min(f(px-1, py), f(px+1, py)), min(f(px, py-1), f(px, py+1))));
	else printf("%lld
", f(px, py));
}