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