题目链接：

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; } 
       
      
     
    
   
  

?

?

?

?