QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#472188#784. 旋转卡壳Bronya#0 1ms3884kbC++14907b2024-07-11 14:56:452024-07-11 14:56:45

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-11 14:56:45]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3884kb
  • [2024-07-11 14:56:45]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
int n;
struct node{
    int x,y;
}a[500005];
int N;
double dist(node x,node y){
    return sqrt(1ll*(x.x-y.x)*(x.x-y.x)+1ll*(x.y-y.y)*(x.y-y.y));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
    N=0;
    for(int i=1;i<=n;i++){
        while(N>=2&&1ll*(a[i].x-a[N].x)*(a[N].y-a[N-1].y)==1ll*(a[N].x-a[N-1].x)*(a[i].y-a[N].y))N--;
        a[++N]=a[i];
    }
    a[N+1]=a[1];
    int now=1,nxet=2;
    double ans=0;
    for(int i=1;i<=N;i++){
        while(1ll*(a[i+1].x-a[i].x)*(a[now].y-a[i].y)-1ll*(a[i+1].y-a[i].y)*(a[now].x-a[i].x)<1ll*(a[i+1].x-a[i].x)*(a[nxet].y-a[i].y)-1ll*(a[i+1].y-a[i].y)*(a[nxet].x-a[i].x)){
            now=nxet;
            nxet=now%N+1;
        }
        ans=max({ans,dist(a[i],a[now]),dist(a[i+1],a[now])});
    }
    printf("%.10lf",ans);
    return 0;
}

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: 3884kb

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:

274336382.4570425749

result:

wrong answer 1st numbers differ - expected: '274339223.1895614', found: '274336382.4570426', error = '0.0000104'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%