QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1004 | #644181 | #784. 旋转卡壳 | Zhou_JK | Zhou_JK | Failed. | 2024-10-16 11:47:27 | 2024-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_JK | 97 | 76ms | 11200kb | C++23 | 2.0kb | 2024-10-16 11:34:49 | 2024-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;
}