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

/ 0评 /

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|

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

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

知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/hdu5626/


发表评论

电子邮件地址不会被公开。 必填项已用*标注