/ Vijos / 题库 /

曼哈顿距离

曼哈顿距离

描述

给出N个D维空间的点。求出曼哈顿距离最大的两个点的
曼哈顿距离。两个点(x1, x2...xD)、(X1,X2..XD)的曼哈顿距
离被定义为|x1-X1|+|x2-X2|+...+|xD-XD|.

格式

输入格式

第一行两个正整数N,D。

接下来有N,每行描述一个点的坐标。

输出格式

在第一行输出曼哈顿距离最大的两个点的曼哈顿距离。

样例1

样例输入1

4 2
2 1
1 4
4 5
5 3

样例输出1

6

限制

1S

提示

在60%的数据中,1<=N<=100000,1<=D<=2
在100%的数据中,1<=N<=100000,1<=D<=5

来源

CQF为noip2009出的练习题

信息

ID
1453
难度
3
分类
其他 | 数学 点击显示
标签
(无)
递交数
294
已通过
139
通过率
47%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库