← 返回题目列表

AtCoder · typical90_br

070. 厂房规划(★4)

中文机器翻译题面 查看原题

配点: 4 点

問題文

在二维平面上 有 N 栋工厂,i 第几号工厂的坐标 (X_i, Y_i) 在

从现在开始,你可以在二维平面上选择任意地点 1 建造发电厂。

当将发电厂的不便之处定义为从发电厂到各工厂的曼哈顿距离总和时,请求出可能出现的最小不便值。顺便说明,在本题的约束条件下答案可以证明为整数。

关于曼哈顿距离 座標 (x_1, y_1) 和坐标 (x_2, y_2) 之间的曼哈顿距离是,|x_1 − x_2| + |y_1 − y_2| 中定义。

制約

  • 1 \leq N \leq 10^5
  • -10^9 \leq X_i, Y_i \leq 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

请以整数输出不便度的最小值。


入力例 1

2
-1 2
1 1

出力例 1

3

发电厂 (0, 1) 通过建造在 ,将从发电厂到各工厂的曼哈顿距离如下。

  • 工場 1 : |-1 - 0| + |2 - 1| = 2
  • 工場 2 : |1 - 0| + |1 - 1| = 1

此时的不便度为 2 + 1 = 3 ,因为无法将不便度小于 3 ,所以 3 。


入力例 2

2
1 0
0 1

出力例 2

2

发电厂 (1, 0) 建设可以得到不便度的最小值 2 可以实现。

另外,如果发电厂建在 (0.5, 0.5) 呀 请注意,它可能是 (0, 1) ,不便度同样为 2 。 对于


入力例 3

5
2 5
2 5
-3 4
-4 -8
6 -2

出力例 3

35

同一坐标上也可能存在多个工厂。


入力例 4

4
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000

出力例 4

8000000000