QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#487724#784. 旋转卡壳mzmz0010 1ms8060kbC++141.2kb2024-07-23 08:15:072024-07-23 08:15:07

Judging History

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

  • [2024-10-16 12:18:36]
  • hack成功,自动添加数据
  • (/hack/1005)
  • [2024-09-24 16:55:39]
  • hack成功,自动添加数据
  • (/hack/888)
  • [2024-07-31 21:52:32]
  • hack成功,自动添加数据
  • (/hack/764)
  • [2024-07-31 21:47:53]
  • hack成功,自动添加数据
  • (/hack/763)
  • [2024-07-23 08:15:07]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:8060kb
  • [2024-07-23 08:15:07]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,top1,top2,q1[500005],q2[500005],tb[500005],tot,md;
ll ans;
struct node{
	ll x,y;
}p[500005];
bool cmp(node x,node y){
	return x.x==y.x?x.y<y.y:x.x<y.x;
}
ll dx(ll x,ll y){
	return p[x].x-p[y].x;
}
ll dy(ll x,ll y){
	return p[x].y-p[y].y;
}
ll get_d(ll x,ll y){
	return dx(x,y)*dx(x,y)+dy(x,y)*dy(x,y);
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
		scanf("%lld%lld",&p[i].x,&p[i].y);
	sort(p+1,p+1+n,cmp);
	for(ll i=1;i<=n;i++){
		if(!(i<n&&p[i].x==p[i+1].x)){
			while(top1>1&&dy(q1[top1],q1[top1-1])*dx(i,q1[top1])<dy(i,q1[top1])*dx(q1[top1],q1[top1-1]))top1--;
			q1[++top1]=i;
		}
		if(!(i>1&&p[i].x==p[i-1].x)){
			while(top2>1&&dy(q2[top2],q2[top2-1])*dx(i,q2[top2])>dy(i,q2[top2])*dx(q2[top2],q2[top2-1]))top2--;
			q2[++top2]=i;
		}
	}
	for(ll i=1;i<=top1;i++)tb[++tot]=q1[i];
	md=tot;
	if(q1[top1]!=q2[top2])tb[++tot]=q2[top2];
	for(ll i=top2-1;i>1;i--)tb[++tot]=q2[i];
	if(q1[1]!=q2[1])tb[++tot]=q2[1];
	
	for(ll i=1,j=md;i<md;i++){
		while(j<tot&&dy(tb[i+1],tb[i])*dx(tb[j],tb[j+1])<dy(tb[j],tb[j+1])*dx(tb[i+1],tb[i]))j++;
		ans=max(ans,get_d(tb[i],tb[j]));
	}
	printf("%lf",sqrt(ans));
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 1ms
memory: 8056kb

input:

1000
0 0
-997615 -8573
-1988394 -28911
-2726572 -44296
-3491635 -60392
-4419752 -82814
-5298550 -105946
-5723430 -118453
-6608257 -147267
-7034966 -161982
-7563964 -181682
-8507871 -222865
-9499799 -271846
-10090186 -303547
-10400262 -322989
-10614073 -339725
-11081438 -378596
-11791568 -439127
-127...

output:

274339223.189561

result:

ok found '274339223.1895610', expected '274339223.1895614', error '0.0000000'

Test #2:

score: 10
Accepted
time: 1ms
memory: 8056kb

input:

1000
0 0
-887614 -1937
-1459359 -3808
-2421409 -24096
-3273181 -48456
-3917594 -76664
-4402753 -100164
-5375022 -150897
-5993935 -192089
-6587159 -238825
-7549680 -333298
-8330993 -416479
-9244392 -515027
-10010900 -598589
-10374584 -640275
-10767641 -686907
-11173081 -741316
-11821952 -833327
-1260...

output:

262687047.927491

result:

ok found '262687047.9274910', expected '262687047.9274906', error '0.0000000'

Test #3:

score: 10
Accepted
time: 1ms
memory: 8060kb

input:

1000
0 0
-631055 -2758
-1328409 -7463
-2248672 -20536
-2412978 -23564
-2659543 -28441
-3383179 -43406
-4183375 -64326
-4856658 -88337
-5799682 -134822
-6757348 -189404
-7132846 -212164
-7563226 -242116
-8368716 -300012
-9321463 -381770
-9831821 -432746
-10409503 -491057
-11360852 -607259
-11874199 -...

output:

257868038.643590

result:

ok found '257868038.6435900', expected '257868038.6435897', error '0.0000000'

Test #4:

score: 10
Accepted
time: 1ms
memory: 8036kb

input:

1000
0 0
-48652 -588
-951356 -20091
-1517426 -33325
-1965414 -51971
-2466111 -74904
-3046762 -103888
-3555833 -132002
-3976901 -156059
-4972848 -245498
-5921476 -332492
-6353035 -375491
-7327511 -496188
-7939064 -575429
-8842272 -694656
-9246222 -756797
-9771758 -860630
-10633761 -1031205
-10981774 ...

output:

259539672.480453

result:

ok found '259539672.4804530', expected '259539672.4804534', error '0.0000000'

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 7984kb

input:

1000
0 0
-456569 -2668
-1141521 -7887
-1270801 -8967
-1971135 -21206
-2919889 -38188
-3903859 -71231
-4752603 -107450
-5508682 -143873
-6214620 -183392
-6718977 -212193
-7452291 -271600
-8408796 -354998
-9261882 -432674
-9528618 -457608
-10099091 -513153
-10320120 -535958
-11067358 -614356
-12050731...

output:

250213042.785528

result:

wrong answer 1st numbers differ - expected: '250217366.4826218', found: '250213042.7855280', error = '0.0000173'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%