QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644122#784. 旋转卡壳Zhou_JK0 1ms3800kbC++232.0kb2024-10-16 11:05:272024-10-16 11:05:28

Judging History

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

  • [2024-10-16 12:18:36]
  • hack成功,自动添加数据
  • (/hack/1005)
  • [2024-10-16 11:05:28]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3800kb
  • [2024-10-16 11:05:27]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cassert>
#include<chrono>
#include<random>
#include<vector>
#include<functional>
#include<iomanip>
#include<algorithm>
using namespace std;
class Point
{
public:
    int x,y;
    Point(){x=0,y=0;}
    Point(const int &_x,const int &_y):x(_x),y(_y) {}
    friend long long cross(const Point &a,const Point &b)
    {
        return (long long)a.x*b.y-(long long)a.y*b.x;
    }
    friend long long dot(const Point &a,const Point &b)
    {
        return (long long)a.x*b.x+(long long)a.y*b.y;
    }
    friend istream &operator>>(istream &in,Point &obj)
    {
        in>>obj.x>>obj.y;
        return in;
    }
    friend ostream &operator<<(ostream &out,const Point &obj)
    {
        out<<obj.x<<" "<<obj.y;
        return out;
    }
    friend Point operator + (const Point &a,const Point &b)
    {
        return Point(a.x+b.x,a.y+b.y);
    }
    Point operator += (const Point &b)
    {
        x+=b.x,y+=b.y;
        return *this;
    }
    friend Point operator - (const Point &a,const Point &b)
    {
        return Point(a.x-b.x,a.y-b.y);
    }
    Point operator -= (const Point &b)
    {
        x-=b.x,y-=b.y;
        return *this;
    }
};
long long distance(const Point &a,const Point &b)
{
    return (long long)(a.x-b.x)*(a.x-b.x)+(long long)(a.y-b.y)*(a.y-b.y);
}
long long convex_diamater(const vector<Point> &g)
{
    int n=g.size();
    long long ans=0;
    for(int i=0,j=0;i<n;i++)
    {
        while(cross(g[i]-g[j],g[(i+1)%n]-g[j])<cross(g[i]-g[(j+1)%n],g[(i+1)%n]-g[(j+1)%n])) j=(j+1)%n;
        ans=max(ans,max(distance(g[j],g[i]),distance(g[j],g[(i+1)%n])));
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int n;
    cin>>n;
    vector<Point> g(n);
    for(int i=0;i<n;i++)
        cin>>g[i];
    long long res=convex_diamater(g);
    long double ans=sqrtl(res);
    cout<<fixed<<setprecision(10)<<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: 3800kb

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

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%