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

文章目录

Problem Description
Input
Output
Sample Input
Sample Output
Translation
Analysis
Code

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|$

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

$x_A-x_B+y_A-y_B \\\\ x_B-x_A+y_A-y_B \\\\ x_A-x_B+y_B-y_A \\\\ x_B-x_A+y_B-y_A$

经过变形，我们可以发现，完全可以令 $A_i=X_i+Y_i,B_i=X_i-Y_i$ ，那么答案就在 $(max(A_i)-min(A_i),max(B_i)-min(B_i))$ 之中了。

Code

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1000005;
const long long INF=1e9;
int T,n,x[maxn],y[maxn];
long long seed;
long long A[maxn],B[maxn],maxa,mina,maxb,minb;

// A[i]=Xi+Yi;
// B[i]=Xi-Yi;

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); 
}

inline void build(int n,int seed){
    for (int i=0;i<n;i++)
        x[i]=rand(-1000000000,1000000000),
        y[i]=rand(-1000000000,1000000000),
        A[i]=x[i]+y[i],maxa=max(maxa,A[i]),mina=min(mina,A[i]),
        B[i]=x[i]-y[i],maxb=max(maxb,B[i]),minb=min(minb,B[i]);
}

inline void init(){
    maxa=maxb=-INF;
    mina=minb=INF;
}

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

int main(){
    T=read();
    while (T--){
        init();
        n=read();seed=read();
        build(n,seed);
        printf("%lld\n",max(maxa-mina,maxb-minb));
    }
    return 0;
}

SkyWT / 博客 / HDU 5626 Clarke and points 题解：一道巧妙的贪心