UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#208666#3765. 差距qiuqiu100698ms5904kbC++111.0kb2024-08-03 09:11:022024-08-03 12:03:15

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize(2)
struct node{int x,y;} p[200005];
int d[200005];
int dis(node a,node b){
	return abs(a.x-b.x)+abs(a.y-b.y);
}
signed main(){
	int n;
	bool v=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&p[i].x,&p[i].y);
		if(p[i].y) v=1;
	}
	if(n<=3000){
		int mx=INT_MIN;
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				mx=max(mx,dis(p[i],p[j]));
		cout<<mx;
	}
	else if(!v){
		int mx=INT_MIN,mn=INT_MAX;
		for(int i=1;i<=n;i++)
			mx=max(mx,p[i].x),mn=min(mn,p[i].x);
		cout<<abs(mx-mn);
	}
	else{
		int mx=INT_MIN;
		for(int i=1;i<=n;i++) d[i]=p[i].x+p[i].y;
		sort(d+1,d+n+1);
		mx=max(mx,abs(d[n]-d[1]));
		for(int i=1;i<=n;i++) d[i]=p[i].x-p[i].y;
		sort(d+1,d+n+1);
		mx=max(mx,abs(d[n]-d[1]));
		for(int i=1;i<=n;i++) d[i]=-p[i].x+p[i].y;
		sort(d+1,d+n+1);
		mx=max(mx,abs(d[n]-d[1]));
		for(int i=1;i<=n;i++) d[i]=-p[i].x-p[i].y;
		sort(d+1,d+n+1);
		mx=max(mx,abs(d[n]-d[1]));
		cout<<mx;
	}
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 13ms
memory: 1260kb

input:

3000
792453998 306958027
996204014 600915334
-981568884 236264724
470759953 606485180
-53238153 -555...

output:

3941875385

result:

ok single line: '3941875385'

Test #2:

score: 10
Accepted
time: 17ms
memory: 1264kb

input:

3000
79975810 212758591
-601603486 -625555123
-708207563 -951706306
774109860 63713456
-946878280 50...

output:

3917242036

result:

ok single line: '3917242036'

Test #3:

score: 10
Accepted
time: 14ms
memory: 1264kb

input:

3000
691369894 -8116153
-443993089 719627429
-784315238 -928459306
271872303 -657587041
245813343 30...

output:

3960933529

result:

ok single line: '3960933529'

Test #4:

score: 10
Accepted
time: 48ms
memory: 4340kb

input:

200000
599323188 0
-843037110 0
518683150 0
-159076766 0
588819428 0
56209470 0
855323935 0
10073519...

output:

1999957119

result:

ok single line: '1999957119'

Test #5:

score: 10
Accepted
time: 55ms
memory: 4340kb

input:

200000
480502842 0
139974590 0
-311006285 0
296111828 0
-96216923 0
491915067 0
741774257 0
70377442...

output:

1999984073

result:

ok single line: '1999984073'

Test #6:

score: 10
Accepted
time: 62ms
memory: 4340kb

input:

200000
-713216891 0
897961748 0
-746428112 0
-906216677 0
-319987275 0
920073294 0
-47674064 0
18432...

output:

1999970653

result:

ok single line: '1999970653'

Test #7:

score: 10
Accepted
time: 131ms
memory: 5904kb

input:

200000
37685867 -780251225
743094375 -127258779
-135245284 -324381032
117211694 -763086777
544186852...

output:

3995976829

result:

ok single line: '3995976829'

Test #8:

score: 10
Accepted
time: 138ms
memory: 5904kb

input:

200000
272655496 813504818
-63935068 844884673
329969667 -935497929
939027783 774905192
63872339 -61...

output:

3988926702

result:

ok single line: '3988926702'

Test #9:

score: 10
Accepted
time: 122ms
memory: 5904kb

input:

200000
931816546 -929771953
478933054 204368625
-513722829 814068200
424836471 -113036793
-288435765...

output:

3989038088

result:

ok single line: '3989038088'

Test #10:

score: 10
Accepted
time: 98ms
memory: 5904kb

input:

200000
559626386 634020933
549422179 -500273550
281287608 320750484
67874874 196515538
-116637058 37...

output:

3994387298

result:

ok single line: '3994387298'

Extra Test:

score: 0
Extra Test Passed