Clarke and points

Problem Description

The Manhattan Distance between point A(XA,YA) and B(XB，YB) is |XA - XB| + |Xb - YB|;
the coordinate of each point is generated by the followed code.
Input
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

这道题原本不难但值得分析；开始一直在纠结两个变量之间的大小关系；因为这关系到去绝对值之后是否要变号的问题；但是还是看了题解。。。

题解:对于二维的变量，由于加了绝对值，则只有两种关系，要不就两个数要都大，这样ans = (Xi+Yi) - (Xj + Yj);同时注意到此时的| (Xi - Yi) - (Xj - Yj) | < | ans |;(两个正数相加肯定大于相减(加了绝对值也是一样)，这时就算计算了另一个对结果也没影响，后面亦同)；若是一大一小，那么ans = (Xi - Yi) - (Xj - Yj);此时满足 |ans| > | (Xi+Yi) - (Xj + Yj) |;

这时能说ans就是取max( | (Xi+Yi) - (Xj + Yj) |,| (Xi - Yi) - (Xj - Yj) | );即维护最大最小的x+y与x - y;

ps:在线算法，节省空间；

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

#include<stack>

#include<set>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define MS0(a) memset(a,0,sizeof(a))

#define MS1(a) memset(a,-1,sizeof(a))

typedef __int64 ll;

template<typename T>

void read1(T &m)

{

    T x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

template<typename T>

void out(T a)

{

    if(a>) out(a/);

    putchar(a%+'');

}

ll n,seed;

inline ll rand(ll l, ll r) {

    static ll mo=1e9+, g=;

    return l+((seed*=g)%=mo)%(r-l+);

}

const ll inf = 0x3f3f3f3f3f3f3f3fLL;

int main()

{

    int T;

    read1(T);

    while(T--){

        read2(n,seed);

        ll mn0 = inf,mn1 = -inf,mx0 = inf,mx1 = -inf,x,y,ans;

        rep0(i,,n){

            x = rand(-, );

            y = rand(-, );

            ll tmp = x + y,temp = x - y;

            mn0 = min(mn0,tmp);mn1 = max(mn1,tmp);

            mx0 = min(mx0,temp);mx1 = max(mx1,temp);

        }

        ans = max(mn1 - mn0,mx1 - mx0);

        out(ans);puts("");

    }

    return ;

}

秒客网

hdu 5626 Clarke and points 数学推理

Clarke and points

相关文章