hdu 5626 Clarke and points (曼哈顿距离变换，拆点)
http://acm.split.hdu.edu.cn/showproblem.php?pid=5626
题意：给出n（1E6）个点的二维坐标，问距离最远的两个点的距离是多少。
思路：对曼哈顿距离进行变换。
先看曼哈顿距离的定义
|x1−x2|+|y1−y2|
拆绝对值
x1−x2+y1−y2或x1−x2+y2−y1
x2−x1+y1−y2或x2−x1+y2−y1
即|x1+y1−(x2+y2)|或|x1−y1−(x2−y2)|
设x1+y1为x′，x1−y1为y′
则|x1′−x2′|或|y1′−y2′|
所以原要求1转化为
max(|x1′−x2′|,|y1′−y2′|)<=c
然后分别对x,y排序即可..最大的距离一定是y[n-1]-y[0]或者x[n-1]-x[0]
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月24日 星期三 23时42分15秒
4File Name :code/hdu/5626.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E6+7;
34LL seed;
35int n;
36int x[N],y[N];
37
38inline LL rand(LL l,LL r)
39{
40 static LL mo =1E9+7,g=78125;
41 return l+((seed*=g)%=mo)%(r-l+1);
42}
43int main()
44{
45 #ifndef ONLINE_JUDGE
46 freopen("code/in.txt","r",stdin);
47 #endif
48 ios::sync_with_stdio(false);
49 int T;
50 cin>>T;
51 while (T--)
52 {
53 cin>>n>>seed;
54 for ( int i = 0 ; i < n ; i++)
55 {
56 int xx,yy;
57 xx = rand(-1000000000,1000000000);
58 yy = rand(-1000000000,1000000000);
59 x[i] = xx-yy;
60 y[i] = xx+yy;
61 }
62 sort(x,x+n);
63 sort(y,y+n);
64 int ans = -1;
65 ans = max(ans,y[n-1]-y[0]);
66 ans = max(ans,x[n-1]-x[0]);
67 cout<<ans<<endl;
68 }
69
70 #ifndef ONLINE_JUDGE
71 fclose(stdin);
72 #endif
73 return 0;
74}