曼哈顿距离

题目链接 # Description # Ayu 在二维平面上收集天使玩偶。初始时平面上有 \( N \) 个玩偶，坐标已知。接下来有 \( M \) 个操作： 发现一个新玩偶，坐标为 \( (x, y) \)。 Ayu 瞬移到了 \( (x, y) \)，需要寻找离当前位置最近的玩偶（曼哈顿距离最小），并输出该最小距离：\( \min_i (|x - x_i| + |y - y_i|) \). Input # 第一行两个整数 \( N, M \)（\( 1 \le N, M \le 5 \times 10^5 \)）。 接下来 \( N \) 行，每行两个整数 \( x_i, y_i \)，表示初始玩偶的坐标。 接下来 \( M \) 行，每行三个整数 \( t, x, y \)：

http://poj.org/problem?id=2926 题意：给出n(1E5)个五维空间内的坐标…问最远的两个点距离多少。 思路：拆点即可。去绝对值。可以由二维空间推广到k维空间。一个点可以拆成2^(k-1)个点。 具体见代码。

http://acm.split.hdu.edu.cn/showproblem.php?pid=5626 题意：给出n（1E6）个点的二维坐标，问距离最远的两个点的距离是多少。 思路：对曼哈顿距离进行变换。 先看曼哈顿距离的定义 |x1−x2|+|y1−y2| 拆绝对值 x1−x2+y1−y2或x1−x2+y2−y1

http://www.lydsy.com/JudgeOnline/problem.php?id=1604 题意：了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的： 1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C. 2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群． 给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛