QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#586136 | #784. 旋转卡壳 | houbur | 0 | 1ms | 6408kb | C++20 | 1.4kb | 2024-09-24 06:39:38 | 2024-09-24 06:39:38 |
Judging History
你现在查看的是最新测评结果
- [2024-10-16 12:18:36]
- hack成功,自动添加数据
- (/hack/1005)
- [2024-09-24 16:55:39]
- hack成功,自动添加数据
- (/hack/888)
- [2024-09-24 06:39:38]
- 提交
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 dis(sb a,sb b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(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 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=1;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];
}
int mx=0,l=1,r=1;
for(int i=1;i<=top;i++){
int op=dis(st[i],st[1]);
if(op>mx){mx=op;r=i;}
else break;
}
double ans=0;
for(l=1;l<=top;l++){
while(r<=top&&dis(st[(r+1)%top+1],st[l])>dis(st[r],st[l]))r=(r+1)%top+1;
// cout<<st[l].x<<' '<<st[l].y<<' '<<st[r].x<<' '<<st[r].y<<endl;
ans=max(ans,sqrt((st[l].x-st[r].x)*(st[l].x-st[r].x)+(st[l].y-st[r].y)*(st[l].y-st[r].y)));
}
printf("%.7lf",ans);
return 0;
}
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: 6380kb
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: 6408kb
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: 1ms
memory: 6348kb
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%