QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584937#784. 旋转卡壳int_R0 1ms5932kbC++141.3kb2024-09-23 17:43:192024-09-23 17:43:19

Judging History

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

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

answer

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<iomanip>
#define int long long
#define double long double
using namespace std;
const int MAXN=1e6+10;
struct Point{int x,y;};
struct Vector{int x,y;};
int n,tot;double ans;
Point p[MAXN],s[MAXN];
Vector operator - (Point x,Point y)
    {return {x.x-y.x,x.y-y.y};}
inline int cross(Vector x,Vector y)
    {return x.x*y.y-x.y*y.x;}
inline double len(Vector x)
    {return sqrt(x.x*x.x+x.y*x.y);}
inline double dist(Point x,Point y,Point z)
    {return (double)cross(y-x,z-(Point){0,0})/2/len(y-x);}
inline bool cmp(Point x,Point y)
    {return x.x!=y.x?x.x<y.x:x.y<y.y;}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>p[i].x>>p[i].y;
    sort(p+1,p+1+n,cmp);
    s[++tot]=p[1];
    for(int i=2;i<=n;++i)
    {
        while(tot>1&&cross(s[tot]-s[tot-1],p[i]-s[tot])<0) --tot;
        s[++tot]=p[i];
    }
    int tmp=tot;
    for(int i=n-1;i>=1;--i)
    {
        while(tot>tmp&&cross(s[tot]-s[tot-1],p[i]-s[tot])<0) --tot;
        s[++tot]=p[i];
    }
    for(int i=1,j=3;i<tot;++i)
    {
        while(dist(s[i+1],s[i],s[j+1])>dist(s[i+1],s[i],s[j]))
            {++j;if(j==tot) j=1;}
        ans=max(ans,max(len(s[j]-s[i-1]),len(s[j]-s[i])));
    }
    cout<<fixed<<setprecision(6)<<ans<<'\n';
}

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

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:

175652508.211503

result:

wrong answer 1st numbers differ - expected: '274339223.1895614', found: '175652508.2115030', error = '0.3597251'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%