Clarke and points

题目连接：

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(xA,yA) and point B(xB,yB) is |xA−xB|+|yA−yB|.

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≤109), 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

Hint

题意

让你求平面两点的曼哈顿最远距离

题解：

显然我们可以看出距离 = abs(x1-x2)+abs(y1-y2)

我们把绝对值拆开，然后再归纳一下，显然可以分为一下四种情况(x1+y1)-(x2+y2),(x1-y1)-(x2-y2),(-x1+y1)-(-x2+y2),(-x1-y1)-(-x2-y2)

我们可以看出减号左右是相同的，所以我们维护这四个值的最大最小值就好了

代码

#include
    
     #include
     
      #include
      
       using namespace std;const int maxn = 1e6+7;int n;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);}long long Max[10];long long Min[10];int main(){    int t;    scanf("%d",&t);    for(int cas=1;cas<=t;cas++)    {        cin >> n >> seed;        for(int i=0;i<10;i++)            Max[i]=-1e15,Min[i]=1e15;        long long x,y;        for (int i = 0; i < n; i++)        {            x = rand(-1000000000, 1000000000),            y = rand(-1000000000, 1000000000);            Max[0]=max(Max[0],x+y);            Max[1]=max(Max[1],-x+y);            Max[2]=max(Max[2],x-y);            Max[3]=max(Max[3],-x-y);            Min[0]=min(Min[0],x+y);            Min[1]=min(Min[1],-x+y);            Min[2]=min(Min[2],x-y);            Min[3]=min(Min[3],-x-y);        }        long long ans = 0;        for(int i=0;i<4;i++)            ans=max(Max[i]-Min[i],ans);        cout<
       
        <