QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#584927 | #784. 旋转卡壳 | int_R | 0 | 1ms | 5988kb | C++14 | 1.3kb | 2024-09-23 17:41:02 | 2024-09-23 17:41:03 |
Judging History
你现在查看的是最新测评结果
- [2024-10-16 12:18:36]
- hack成功,自动添加数据
- (/hack/1005)
- [2024-09-24 16:55:39]
- hack成功,自动添加数据
- (/hack/888)
- [2024-09-23 17:41:02]
- 提交
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-x)/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';
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5988kb
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%