Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom12月前

12/6
21:20
计算几何

[bzoj 3170] [Tjoi 2013]松鼠聚会

♦♦♦♦♦♦   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

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

%%%PoPoQQQ大爷

原稳:http://blog.csdn.net/PoPoQQQ/article/details/42100273

给定平面上的n个点,求这n个点中的一个点到这n个点的切比雪夫距离之和最小

切比雪夫距离,即各坐标差绝对值的最大值

首先我们如果想把曼哈顿距离转化成切比雪夫距离 那么就要把点(x,y)变成(x+y,x-y) 这样新点之间的切比雪夫距离就是原点之间的曼哈顿距离

同理,我们可以把切比雪夫距离转化成曼哈顿距离 即把点(x,y)变成((x+y)/2,(x-y)/2)

然后将横纵坐标排序 维护前缀和 分开讨论横纵坐标的曼哈顿距离即可

 

[bzoj 3170] [Tjoi 2013]松鼠聚会