一类平面点对曼哈顿距离问题的探究 常州市第一中学 陈 子 旸 曼哈顿距离问题在信息学竞赛题目中 十分常见 曼哈顿距离的定义：在欧几里得空间 的固定直角坐标系上两点所形成的线 段对轴产生的投影的距离总和 讨论将围绕一类平面上最大、最小曼 哈顿距离点对问题展开目录 引例 情况一：离线查询、无修改 情况二：在线查询、修改 情况三：在线查询、无修改 其他方法的讨论 总结引例 (magic)题目大意 ：在一个(k=7) 维的空间中，有 (n=100000)个点 ，要求求出在这些 点对中曼哈顿距离 最远的点对之间的 曼哈顿距离。例题分析 直接暴力枚举点对？ 显然TLE！ 两点间曼哈顿距离的计算公式： 以平面为例 dist= |x1-x2|+|y1-y2| 绝对值处理太麻烦！ dist= |(x1-y1)-(x2-y2)| ,(x1x2 & y1y2)|(x1x2 & y1x2 & y1y2)|(x1y2)例题分析 怎么处理？ 分类讨论？ ！完全不需要！ |x|+|y|=|x+y| 也就是说： 如果我们计算时如果不满足条件，所计算 出的值会比真实值小，不会更新答案！例题分析 处理时，只需要分别统计
