F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

Clarke and points

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 714    Accepted Submission(s): 486

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 \le T \le 5)$, the number of test case.
For each test case, a line followed, contains two integers $n, seed(2 \le n \le 1000000, 1 \le seed \le 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

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-09-21 11:47:00, Gzip enabled Administration