Clarke and points
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 306 Accepted Submission(s): 219
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(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
問題描述
克拉克是一名精神分裂患者。某一天克拉克變成了一位幾何研究學者。
他研究一個有趣的距離,曼哈頓距離。點A(x_A, y_A)A(xA,yA)和點B(x_B, y_B)B(xB,yB)的曼哈頓距離為|x_A-x_B|+|y_A-y_B|∣xA−xB∣+∣yA−yB∣。
現在他有nn個這樣的點,他需要找出兩個點i, ji,j使得曼哈頓距離最大。
輸入描述 第一行是一個整數T(1 \le T \le 5)T(1≤T≤5),表示資料組數。
每組資料第一行為兩個整數n, seed(2 \le n \le 1000000, 1 \le seed \le 10^9)n,seed(2≤n≤1000000,1≤seed≤109),表示點的個數和種子。
nn個點的坐标是這樣得到的:
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);
輸出描述 對于每組資料輸出一行,表示最大的曼哈頓距離。
輸入樣例 2
3 233
5 332
輸出樣例 1557439953
1423870062
//思路: 這塊用到一點數學的知識,就是去絕對值,總共有四種情況(應該都知道),但列出來之後會發現可以合并成兩種情況。 情況一:(Xa+Ya)-(Xb+Yb); 情況二:(Xa-Ya)-(Xb-Yb); 是以隻用求出這兩種情況的最大值即為所求。。 #include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ll long long
#define N 1000010
using namespace std;
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);
}
int main()
{
int t,n,i;
scanf("%d",&t);
while(t--)
{
scanf("%d%lld",&n,&seed);
ll x1=-INF,x2=-INF;
ll y1=INF,y2=INF;
for (i = 0; i < n; i++)
{
ll x,y;
x = rand(-1000000000, 1000000000);
y = rand(-1000000000, 1000000000);
x1=max(x1,x+y);x2=max(x2,x-y);
y1=min(y1,x+y);y2=min(y2,x-y);
}
ll sum=max(x1-y1,x2-y2);
printf("%lld\n",sum);
}
return 0;
}