5536: 切比雪夫距离之和最小
[Creator : ]
Description
假设有两个点坐标为 $(x_1, y_1)$ 与 $(x_2, y_2)$，它们之间的切比雪夫距离定义为 $max{(\lvert x_1−x_2 \rvert,\ \lvert y_1−y_2 \vert)}$。
在平面上有 $n\ (1≤n≤10^5)$ 个点，第 $i$ 个点的座位为 $(x_i,\ y_i)$。
请在这 $n$ 个点找，找出一个点做为中心点。使得该点到其他所有点的切比雪夫距离最小。
在平面上有 $n\ (1≤n≤10^5)$ 个点，第 $i$ 个点的座位为 $(x_i,\ y_i)$。
请在这 $n$ 个点找，找出一个点做为中心点。使得该点到其他所有点的切比雪夫距离最小。
Input
第一行一个正整数 $n$，表示有 $n$ 个点。
其后 $n$ 行，每行两个整数 $x_i,\ y_i,\ (−10^9≤x_i,\ y_i≤10^9)$。
其后 $n$ 行，每行两个整数 $x_i,\ y_i,\ (−10^9≤x_i,\ y_i≤10^9)$。
Output
一个整数，表示最小的切比雪夫距离之和。
Sample 1 Input
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
Sample 1 Output
26
这个样例中，$(-1\ -2)$ 做为中心点的时候，切比雪夫距离之和最小。
Sample 2 Input
6
0 0
2 0
-5 -2
2 -2
-1 2
4 0
Sample 2 Output
20
这个样例中，$(-1\ -2)$ 做为中心点的时候，切比雪夫距离之和最小。
Sample 3 Input
10
-1 -1
-3 2
-4 4
5 2
5 -4
3 -1
4 3
-1 -2
3 4
-2 2
Sample 3 Output
56
这个样例中，$(-1\ -2)$ 做为中心点的时候，切比雪夫距离之和最小。