题目：

草原上住着一群小松鼠,每个小松鼠都有一个家。时间长了,大家觉得应该聚一聚。但是草原非常大,松鼠们都很头疼应该在谁家聚会才最合理。

每个小松鼠的家可以用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点(x-1,y),(x+1,y),(x,y-1),(x,y+1),(x-1,y+1),(x-1,y-1),(x+1,y+1), (x+1,y-1)距离为1。

输入

第一行是一个整数N,表示有多少只松鼠。接下来N行,第i行是两个整数x和y,表示松鼠i的家的坐标。(0≤N≤105,−109≤x,y≤109)

输出

一个整数,表示松鼠为了聚会走的路程和最小是多少。

样例输入1

6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2

样例输出1

20

样例输入2

6
0 0
2 0
-5 -2
2 -2
-1 2
4 0

样例输出2

15

提示

在第一个样例中,松鼠在第二只松鼠家(-1,-2)聚会;在第二个样例中,松鼠在第一只松鼠家(0,0)聚会

题解：此题中定义的两点间距离，稍加分析就会发现是max(|xi-xj|， |yi-yj|);

此时需要用到一个公式:

　　　　　　　　max（|a|,|b|）=|（a+b）/2|+|（a-b）/2|;

于是，两点间距离成了:

　　　　　　　　|(xi-xj+yi-yj)/2|+|(xi-xj-yi+yj)/2|

　　　　　　=   (|(xi+yi) - (xj+yj)| + |(xi-yi)-(xj-yj)|)/2

公式中需要用xi+yi, xi-yi的值，这其实对应于点(xi,yi)在另一个坐标系中的坐标。我们对原来的点坐标做变换，令x'=x+y, y'=x-y,则上面的公式变成了：

　　　　　　　　(|xi'-xj'| + |yi'-yj'|)/2

分析到这儿就好做了，对于给定的点pi, 计算∑(|xi'-xj'| + |yi'-yj'|)/2还是很容易的，先整体做一遍预处理，按x排序计算一遍x坐标的前缀和，再按y排序，计算一次y坐标的前缀和就可以了。

代码如下：

#include
#include
#include
using namespace std;
#define ll long long
#define N 101000
struct point {
ll x, y;
ll sx, sy;
int cx, cy;
}p[N];

ll sumx, sumy;

bool cmpx(point a, point b){
return a.x < b.x;
}

bool cmpy(point a, point b){
return a.y < b.y;
}

int main()
{
int n;
while(~scanf("%d", &n))
{
sumx = sumy = ;
ll x, y;
for(int i = ; i < n; i++)
{
scanf("%lld %lld", &x, &y);
p[i].x = x+y, p[i].y = x-y;
sumx += p[i].x, sumy += p[i].y;
}
sort(p, p+n, cmpx);
p[].sx = p[].cx = ;
for(int i = ; i < n; i++)
{
p[i].sx = p[i-].sx + p[i-].x;
p[i].cx = p[i-].cx + ;
}

     sort(p, p+n, cmpy);  
     p\[\].sy = p\[\].cy = ;  
     for(int i = ; i < n; i++)  
     {  
         p\[i\].sy = p\[i-\].sy + p\[i-\].y;  
         p\[i\].cy = p\[i-\].cy + ;  
     }  
     ll ans = -;  
     for(int i = ; i < n; i++)  
     {  
         ll tm = p\[i\].cx\*p\[i\].x - p\[i\].sx + (sumx-p\[i\].sx-p\[i\].x)-((n-p\[i\].cx-)\*p\[i\].x);  
         tm += p\[i\].cy\*p\[i\].y - p\[i\].sy + (sumy-p\[i\].sy-p\[i\].y)-((n-p\[i\].cy-)\*p\[i\].y);  
         if(ans == - || tm < ans)ans = tm;  
     }  
     printf("%lld\\n", ans/);  
 }  
 return ;  

}