hdu 5626 Clarke and points

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

Input

The first line contains a integer

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

BestCoder Round #72 (div.2)

先附上自己的写法，运气好的话可以过，运气不好的话超时，这东西也看人品？

 1 #pragma comment(linker, "/STACK:1024000000,1024000000")
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<math.h>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<set>
10 #include<bitset>
11 #include<map>
12 #include<vector>
13 #include<stdlib.h>
14 using namespace std;
15 #define ll long long
16 #define eps 1e-10
17 #define MOD 1000000007
18 #define N 1000006
19 #define inf 1e12
20 
21 struct node{  
22     ll x,y;  
23 }e[N],res[N];  
24 ll cmp(node a,node b)  
25 {  
26     if(a.x==b.x)return a.y<b.y;  
27     return a.x<b.x;  
28 }  
29 ll cross(node a,node b,node c)//向量积  
30 {  
31     return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);  
32 }  
33 ll convex(ll n)//求凸包上的点  
34 {  
35     sort(e,e+n,cmp);  
36     ll m=0,i,j,k;  
37     //求得下凸包，逆时针  
38     //已知凸包点m个，如果新加入点为i，则向量(m-2,i)必定要在(m-2,m-1)的逆时针方向才符合凸包的性质  
39     //若不成立，则m-1点不在凸包上。  
40     for(i=0;i<n;i++)  
41     {  
42         while(m>1&&cross(res[m-1],e[i],res[m-2])<=0)m--;  
43         res[m++]=e[i];  
44     }  
45     k=m;  
46     //求得上凸包  
47     for(i=n-2;i>=0;i--)  
48     {  
49         while(m>k&&cross(res[m-1],e[i],res[m-2])<=0)m--;  
50         res[m++]=e[i];  
51     }  
52     if(n>1)m--;//起始点重复。  
53     return m;  
54 }  
55 
56 long long n,seed;
57 inline long long rand(long long l, long long r) {
58     static long long mo=1e9+7, g=78125;
59     return l+((seed*=g)%=mo)%(r-l+1);
60 }
61 
62 int main()
63 {
64     int t;
65     scanf("%d",&t);
66     while(t--){
67         cin >> n >> seed;
68         for (int i = 0; i < n; i++){
69             e[i].x = rand(-1000000000, 1000000000),
70             e[i].y = rand(-1000000000, 1000000000);
71         }
72         ll    m=convex(n);
73         ll ans=-1;
74         for(ll i=0;i<m;i++){
75             for(ll j=i+1;j<m;j++){
76                 ll cnt = abs(res[i].x-res[j].x)+abs(res[i].y-res[j].y);
77                 ans=max(ans,cnt);
78             }
79         }
80         printf("%I64d
",ans);
81         
82     }        
83     return 0;
84 }

View Code

官方题解：

 1 #include<bitset>
 2 #include<map>
 3 #include<vector>
 4 #include<cstdio>
 5 #include<iostream>
 6 #include<cstring>
 7 #include<string>
 8 #include<algorithm>
 9 #include<cmath>
10 #include<stack>
11 #include<queue>
12 #include<set>
13 #define inf 0x3f3f3f3f
14 #define mem(a,x) memset(a,x,sizeof(a))
15 
16 using namespace std;
17 
18 typedef long long ll;
19 typedef unsigned long long ull;
20 typedef pair<int,int> pii;
21 
22 inline int in()
23 {
24     int res=0;char c;int f=1;
25     while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
26     while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
27     return res*f;
28 }
29 const int  N = 1000003;
30 
31 ll a[N][3];
32 int n;
33 long long seed;
34 inline long long rand(long long l, long long r) {
35     static long long mo=1e9+7, g=78125;
36     return l+((seed*=g)%=mo)%(r-l+1);
37 }
38 int main() {
39     int T;
40     for (scanf("%d", &T);T--;) {
41         cin >> n >> seed;
42         for (int i=0; i<n; i++)
43             a[i][0]=rand(-1000000000, 1000000000),
44             a[i][1]=rand(-1000000000, 1000000000);
45         ll t=0;
46         ll ans=0,mx=-9223372036854775808LL,mn=9223372036854775807LL;
47         for (int s=0; s<(1<<2); s++) {
48             mx=-9223372036854775808LL,mn=9223372036854775807LL;
49             for (int i=0; i<n; i++) {
50                 t = 0;
51                 for (int j=0; j<2; j++)
52                     if ((1<<j) & s) t += a[i][j];
53                     else t -= a[i][j];
54                 mn = min(mn, t);
55                 mx = max(mx, t);
56             }
57             ans = max(ans, mx-mn);
58         }
59         printf("%I64d
", ans);
60     }
61     return 0;
62 }

View Code