3170: [Tjoi 2013]松鼠聚会

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1318  Solved: 664

[][][]

Description

有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。

Input

第一行给出数字N，表示有多少只小松鼠。0<=N<=10^5

下面N行，每行给出x,y表示其家的坐标。

-10^9<=x,y<=10^9

Output

表示为了聚会走的路程和最小为多少。

Sample Input

6

-4 -1

-1 -2

2 -4

0 2

0 3

5 -2

Sample Output

20

　　这道题貌似纯考小知识点吧……

　　不得不说做这道题挺长姿势的，科普一下：欧几里德距离，曼哈顿距离，切比雪夫距离（在这里博主不介绍在数学其他方面的定义，用途）。

　　　　欧几里德距离： 两点间的直线距离。（sqrt((x1-x2)^2+(y1-y2)^2)

）

　　　　曼哈顿距离（出租车几何）：两个点在标准坐标系上的绝对轴距总和。（|x1-x2|+|y1-y2|）。

　　　　切比雪夫距离（棋盘距离）：在国际象棋中国王到其他点的距离。（max(|x1-x2|,|y1-y2|)

）。

　　这三个距离各有各的用处，这道题主要涉及的是曼哈顿距离和切比雪夫距离的转化。

　　首先先明确一点，松鼠家之间的距离是切比雪夫距离，即我们先斜着走，在横着或竖着走，显而易见是最快的。

　　但是，这样我们只能写出n^2打法，过这道题还是不太可能。因此，我们需要一个神奇的东西：切比雪夫距离转曼哈顿距离。

　　　　设两个点为(x1,y1)(x2,y2)

把两个点换成(x1+y1,x1-y1)(x2+y2,x2-y2)他们的曼哈顿距离除二就是(x1,y1)(x2,y2)的切比雪夫距离。

　　剩下的，我们利用前缀和就可以做到了。

　　至于证明，网上很多。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
             
               8 #include 
              
                9 #include