题目链接：
www.2cto.com
题意：给定平面坐标上n（n<=100000）个点，然后在其中选一个，使得所有点到当前点的Chebyshev距离和最小。
?
分析：
切比雪夫距离：设a(x1,y1),b(x2,y2);DIS = max(|x1-x2|,|y1-y2|) = (|x1-x2+y1-y2|+|x1-x2-y1+y2|)/2;
我们将点aa的坐标看成（x1+y1,x1-y1）,bb的坐标看成（x2+y2,x2-y2）,从几何意义上讲相当于点在原
坐标系上逆时针旋转45度，并将坐标扩大√2倍。
然后求新的的最小的曼哈顿距离和的一半即可。
?
代码如下：
?
#include
#include
#include
#include
#include
using namespace std; typedef long long LL; const int maxn = 1e5+10; struct point{ int x,y; LL sum; }p[maxn]; bool cmp1(point A,point B) { if(A.x
= 1; --i) { p[i].sum += sum - (n-i) * p[i].x; sum += p[i].x; } sum = 0; sort(p+1, p+1+n, cmp2); for (LL i = 1; i <= n; ++i) { p[i].sum += (i-1) * p[i].y -sum; sum += p[i].y; } sum = 0; LL ans = 1LL<<62; for (LL i = n; i >= 1; --i) { p[i].sum += sum - (n-i) * p[i].y; ans = min(ans, p[i].sum); sum += p[i].y; } printf(%I64d ,ans/2); } return 0; }
?
?
?
?
??