QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1004#644181#784. 旋转卡壳Zhou_JKZhou_JKFailed.2024-10-16 11:47:272024-10-16 11:47:45

详细

Extra Test:

Accepted
time: 0ms
memory: 3840kb

input:

9
-986 524
-967 -770
-795 -896
79 -967
996 -924
1000 925
618 937
-465 881
-966 689

output:

2596.5581064170

result:

ok found '2596.5581064', expected '2596.5581064', error '0.0000000'

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#644181#784. 旋转卡壳Zhou_JK97 76ms11200kbC++232.0kb2024-10-16 11:34:492024-10-16 12:23:11

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cassert>
#include<chrono>
#include<random>
#include<vector>
#include<functional>
#include<iomanip>
#include<algorithm>
using namespace std;
#define int long long
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=2;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;
}
signed 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;
}