HDU 5626 Clarke and points 题解：一道巧妙的贪心

Link: HDU 5626 Clarke and points

Problem Description

Clarke is a patient with multiple personality disorder. One day he turned into a learner of geometric. He did a research on a interesting distance called Manhattan Distance. The Manhattan Distance between point $A(x_A,y_A)$ and point $B(x_B,y_B)$ is $|x_A−x_B|+|y_A−y_B|$. Now he wants to find the maximum distance between two points of n points.

Input

The first line contains a integer $T(1≤T≤5)$, the number of test case. For each test case, a line followed, contains two integers n,seed $(2≤n≤1000000,1≤seed≤10^9)$, denotes the number of points and a random seed. The coordinate of each point is generated by the followed code.

long long seed;
inline long long rand(long long l, long long r) {
  static long long mo=1e9+7, g=78125;
  return l+((seed*=g)%=mo)%(r-l+1);
}

// ...

cin >> n >> seed;
for (int i = 0; i < n; i++)
  x[i] = rand(-1000000000, 1000000000),
  y[i] = rand(-1000000000, 1000000000);

Output

For each test case, print a line with an integer represented the maximum distance.

Sample Input

2
3 233
5 332

Sample Output

1557439953
1423870062

Translation

给你 N 个点的坐标，求出这 N 个点组成的点对之间曼哈顿距离最大值。

曼哈顿距离：

The Manhattan Distance between point $A(x_A,y_A)$ and point $B(x_B,y_B)$ is $|x_A−x_B|+|y_A−y_B|$.

Analysis

一看到这题，很容易令人想起“平面最近点对”问题。但是实际上这题和那题没有丝毫关系……

其实可以观察这个曼哈顿距离公式：

$|x_A−x_B|+|y_A−y_B|$

那么去绝对值，我们可以分类讨论四种最大值情况：