#P1632. 点的移动
点的移动
题目描述
平面上有 个整数坐标点。如果将点 移动到 ,则需要的代价为 。求使得 个点在同一位置上最少需要的代价。
输入格式
第一行一个正整数 ;
接下来 行,每行两个正整数 和 ,为第 个点的坐标,不超过 。
【数据规模】。
对于 的数据中,满足 。
输出格式
输出共 行,第 行为使得有 个点在统一位置的最少代价。
4
15 14
15 16
14 15
16 15
0
2
3
4
平面上有 N 个整数坐标点。如果将点 (x0,y0) 移动到 (x1,y1),则需要的代价为 ∣x0−x1∣+∣y0−y1∣。求使得 K(K=1,⋯,N) 个点在同一位置上最少需要的代价。
第一行一个正整数 N;
接下来 N 行,每行两个正整数 xi 和 yi,为第 i 个点的坐标,不超过 106。
【数据规模】。
对于 100% 的数据中,满足 1≤N≤50。
输出共 N 行,第 i 行为使得有 i 个点在统一位置的最少代价。
4
15 14
15 16
14 15
16 15
0
2
3
4