QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#586627#784. 旋转卡壳houbur0 1ms6488kbC++201.4kb2024-09-24 14:44:202024-09-24 14:44:21

Judging History

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

  • [2024-10-16 12:18:36]
  • hack成功,自动添加数据
  • (/hack/1005)
  • [2024-09-24 16:55:39]
  • hack成功,自动添加数据
  • (/hack/888)
  • [2024-09-24 14:44:21]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:6488kb
  • [2024-09-24 14:44:20]
  • 提交

answer

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=5e5+5;
int n,m,top,xx,yy;
struct sb{
	double x,y,k;
}e[N],st[N];
inline bool cmp(sb a,sb b){return (a.y==b.y)?(a.x<b.x):(a.y<b.y);}
inline double cross(sb a,sb b,sb c){return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline double ddd(sb a,sb b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline double dis(sb a,sb b,sb c){
	double k=(b.y-c.y)/(b.x-c.x);
	double bb=b.y-k*b.x;
	return fabs(k*a.x-a.y+bb)/sqrt(k*k+1);
}
inline bool cmpp(sb a,sb b){
	if(a.k!=b.k)return a.k<b.k;
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
signed main(){
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>e[i].x>>e[i].y;
	sort(e+1,e+1+n,cmp);
	st[++top]=e[1];
	xx=st[top].x,yy=st[top].y;
	for(int i=2;i<=n;i++)e[i].k=atan2(e[i].y-yy,e[i].x-xx);
	sort(e+2,e+1+n,cmpp);
	st[++top]=e[2];
	for(int i=3;i<=n;i++){
		while(top>1&&cross(st[top-1],st[top],e[i])<=0)top--;
		st[++top]=e[i];
	}st[++top]=st[1];
	int l=1,r=1;
	double ans=0;
	for(l=1;l<top;l++){
		while(dis(st[r%top+1],st[l+1],st[l])>dis(st[r],st[l+1],st[l]))r=r%top+1;
		ans=max({ans,ddd(st[r],st[l]),ddd(st[r],st[l+1])});
	}
	printf("%.7lf",ans);
	return 0;
}/*10
0 0
100 -900
200 -1799
9800 -1799
9900 -900
10000 0
9999 100
9998 199
2 199
1 100
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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.1895614

result:

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

Test #2:

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

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.9274906

result:

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

Test #3:

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

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:

257866364.6433066

result:

wrong answer 1st numbers differ - expected: '257868038.6435897', found: '257866364.6433066', error = '0.0000065'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%