QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487760#784. 旋转卡壳mzmz0010 1ms8084kbC++141.3kb2024-07-23 09:44:302024-07-23 09:44:32

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 09:44:32]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:8084kb
  • [2024-07-23 09:44:30]
  • 提交

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;
	node operator - (const node &b)const{
		return {x-b.x,y-b.y};
	}
	ll operator * (const node &b)const{
		return x*b.y-y*b.x;
	}
}p[500005];
bool cmp(node x,node y){
	return x.x==y.x?x.y<y.y:x.x<y.x;
}
ll dis(node x,node y){
	return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.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&&(p[q1[top1]]-p[q1[top1-1]])*(p[i]-p[q1[top1]])>=0)top1--;
			q1[++top1]=i;
		}
		if(!(i>1&&p[i].x==p[i-1].x)){
			while(top2>1&&(p[q2[top2]]-p[q2[top2-1]])*(p[i]-p[q2[top2]])<=0)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];
	
//	cout<<md<<" ";
//	for(int i=1;i<=tot;i++)cout<<tb[i]<<" ";
//	cout<<endl;
	for(ll i=1,j=md;i<=md;i++){
		while(j<tot&&(p[tb[i+1]]-p[tb[i]])*(p[tb[j]]-p[tb[j-1]])<=0)ans=max(ans,dis(p[tb[i]],p[tb[j]])),j++;
//		cout<<i<<" "<<j<<endl;
		ans=max(ans,dis(p[tb[i]],p[tb[j]]));
	}
	printf("%lf",sqrt(ans));
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 8084kb

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:

274335204.286822

result:

wrong answer 1st numbers differ - expected: '274339223.1895614', found: '274335204.2868220', error = '0.0000146'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%