QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#479681#4739. Pionektjsyykkk0 0ms3952kbC++11964b2024-07-15 20:06:122024-07-15 20:06:13

Judging History

你现在查看的是最新测评结果

  • [2024-07-15 20:06:13]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3952kb
  • [2024-07-15 20:06:12]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
struct vec{
	int x,y;
	vec friend operator+(vec a,vec b){
		return {a.x+b.x,a.y+b.y};
	}
	vec friend operator-(vec a,vec b){
		return {a.x-b.x,a.y-b.y};
	}
	int norm(){
		return x*x+y*y;
	}
	int det(vec b){
		return x*b.y-y*b.x;
	}
	int dot(vec b){
		return x*b.x+y*b.y;
	}
	int get(){
		return y>0||(y==0&&x>=0);
	}
}v[600005];
bool cmp(vec a,vec b){
	if(a.get()==b.get())return a.det(b)>0;
	return a.get()>b.get();
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&v[i].x,&v[i].y);
	sort(v+1,v+n+1,cmp);
	for(int i=1;i<=n;i++)v[i+n]=v[i];//cout<<v[i].x<<" "<<v[i].y<<" "<<v[i].a<<endl;
	vec now=v[0];
	for(int l=1,r=0;l<=n;l++){
		now=now-v[l-1];ans=max(ans,now.norm());
		while(r+1<l+n&&v[l].det(v[r+1])>=0)now=now+v[++r],ans=max(ans,now.norm());
		//cout<<l<<" "<<r<<" "<<now.norm()<<endl;
	}
	printf("%lld",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 15
Accepted
time: 0ms
memory: 3952kb

input:

5
2 -2
-2 -2
0 2
3 1
-3 1

output:

26

result:

ok 1 number(s): "26"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

1
-2 3

output:

13

result:

ok 1 number(s): "13"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

20
-3 -8
-5 -5
-4 2
4 -4
-5 -4
-8 9
-4 1
-2 -3
2 0
-2 -10
-7 7
4 3
-7 2
-5 -3
-9 -9
1 6
7 -9
-8 8
7 -9
10 -2

output:

4930

result:

ok 1 number(s): "4930"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

20
10 6
-9 7
-5 5
10 -10
6 9
0 9
5 8
8 4
7 -9
4 -4
-7 10
-8 -8
-2 -3
-8 -6
7 2
10 -1
-5 9
-6 8
3 -8
-4 1

output:

6084

result:

ok 1 number(s): "6084"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

15
-7 -4
8 -6
-6 -10
-10 8
-2 2
4 -8
-3 -2
-6 -10
6 -2
-8 -2
2 -9
2 3
4 8
5 -3
-10 5

output:

3161

result:

ok 1 number(s): "3161"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

17
3 6
7 6
-2 -3
0 6
9 -10
7 10
10 6
1 -6
6 10
-2 0
-2 10
7 -7
5 0
-2 -2
5 -10
10 8
-10 0

output:

5960

result:

ok 1 number(s): "5960"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

20
5 3
6 3
2 -1
10 4
5 3
9 3
3 0
9 5
4 1
3 2
4 1
7 3
10 5
7 2
1 -1
7 4
8 2
7 4
5 3
8 4

output:

16900

result:

ok 1 number(s): "16900"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

20
-10 0
-9 -7
-10 -9
-5 -1
-3 -1
-4 -3
-1 -1
-6 -4
-2 0
-2 -1
-3 0
-8 -8
-1 1
-7 -6
-8 -5
-10 1
-1 1
-5 -2
-1 -1
-8 -8

output:

13732

result:

ok 1 number(s): "13732"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

18
-4 -1
-3 -2
-4 -2
-2 -1
-2 -6
-2 -5
-4 -3
-2 -3
-2 -4
-3 -4
-2 -2
-4 -5
-3 -1
-4 -4
-3 -5
-4 -6
-3 -3
-3 -6

output:

6885

result:

ok 1 number(s): "6885"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

10
20 20
20 20
-3 1
6 7
-7 7
-8 1
-8 -4
3 8
-11 0
7 7

output:

7162

result:

ok 1 number(s): "7162"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

2
5 1
-3 1

output:

26

result:

ok 1 number(s): "26"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

5
0 0
1 0
0 -1
-1 0
0 1

output:

2

result:

ok 1 number(s): "2"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

1
0 0

output:

0

result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

20
-9693 -7744
2520 1026
-5879 849
-8041 3096
-1545 3561
-5868 -2837
-7782 3883
4796 -5969
-9985 8487
-3980 -2196
-5221 2690
-1276 -4804
-9865 4738
-1731 7643
3532 3744
-1098 5673
7946 -3322
5394 -4151
7731 -1245
-6815 5955

output:

7149019813

result:

ok 1 number(s): "7149019813"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

20
-71 -89
2 -80
-52 -67
29 -75
-11 -81
-84 -70
-6 19
-66 -39
26 -29
0 0
-24 -99
-41 -46
-24 -67
17 -100
12 -21
-7 -8
-70 -3
-59 -86
-2 -76
-31 -25

output:

1333657

result:

ok 1 number(s): "1333657"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

19
650 -8506
5441 7585
931 8335
4514 3241
0 0
-3047 -4121
9780 -9197
-4941 3027
9856 6796
1999 9834
-9399 9246
-9171 635
-5135 5138
7869 -6754
6393 6129
4990 -8773
-4369 -9981
-7943 1326
9654 6069

output:

4650151969

result:

ok 1 number(s): "4650151969"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

19
5850 -1938
6990 5919
-6253 -8379
3481 7134
356 -6789
9091 9279
8230 4407
7409 -8505
-8684 6824
5249 4317
-2452 -5027
-5099 3504
4142 6760
2901 9666
7915 5044
9202 -2769
-9593 -755
-9187 8379
0 0

output:

6510202196

result:

ok 1 number(s): "6510202196"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

19
-5066 -9258
5746 -7684
4216 -6255
8142 9502
1002 4743
-3557 -9283
2173 -3183
9877 9564
6591 9663
1149 -5284
0 0
4163 8825
-4052 9908
-680 2365
1766 -6213
-9265 -1428
-2219 -1030
1308 2861
3039 4899

output:

4748801000

result:

ok 1 number(s): "4748801000"

Test #19:

score: -15
Wrong Answer
time: 0ms
memory: 3812kb

input:

19
801 73
-6234 5916
-9633 -2691
-7037 6320
4555 -3858
-6419 -285
2222 7073
6166 -2174
9978 -8897
1856 1687
8222 2436
-3386 2352
-8397 -9699
8530 -1454
4091 -4421
0 0
8103 -5564
-603 -3953
-4963 -7065

output:

2475469906

result:

wrong answer 1st numbers differ - expected: '3355302226', found: '2475469906'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%