4000: 坐标移动

内存限制：512 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：4 解决：3

题目描述

平面上分布了 � 个点，每个点的坐标都是一个整数。假设将一个点（�1,�1）移动到另一个点（�2,�2）的代价为两点之间的曼哈顿距离，也就是最小代价为 ∣�1−�2∣+∣�1−�2∣。

请求出，从平面中给定的点中，任意取出 � （�=1,2...,�） 个点，这 � 个点移动到同一个点上最小总代价是多少？

输入

第一行一个正整数 �。

接下来 � 行，每行两个正整数 �� 和 �� ，为第 � 个点的坐标，坐标的值不超过 106 的非负整数。

输出

输出共 � 行，第 � 行为使得 � 个点在同一位置的最少代价。

样例输入 复制 

3
1 2
5 6
3 4

样例输出 复制 

0
4
8

提示

样例

输入
复制 

3
1 2
5 6
3 4

输出
复制 

0
4
8

输入
复制 

4 
15 14
15 16
14 15
16 15

输出
复制 

0
2
3
4

输入
复制 

15
1 6
2 4
2 10
12 14
9 14
13 90
25 31
9 9
7 30
7 13
0 4
14 10
10 5
1 34
3 36

输出
复制 

0
2
4
11
19
28
35
47
60
75
95
125
155
194
277
说明

样例 1 解释

从 3 个点中选 1 个点，移到同一个点的最小代价是 0 ，只有 1 个点不需要移动；

从 3 个点中选 2 个点，移到同一个点的最小代价是 4 ，可以将 (1,2) 点移动到 (3,4) 点；

从 3 个点中选 3 个点，移动到同一个点的最小代价是 8 ，可以将 (1,2) 点移动到 (3,4) 点，代价是 4 ；再将 (5,6) 点也移动到 (3,4) 点，代价也是 4 ，因此最小代价是 8 。

数据范围

对于 100% 的数据，满足 1≤�≤50 ，每个坐标的值均为不超过 106 的非负整数。

来源/分类

提交提交记录统计露一手!