QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#888 | #586632 | #784. 旋转卡壳 | houbur | houbur | Success! | 2024-09-24 16:55:20 | 2024-09-24 16:55:20 |
详细
Extra Test:
Wrong Answer
time: 0ms
memory: 6272kb
input:
3 -1 18 1 6 3 -6
output:
12.1655251
result:
wrong answer 1st numbers differ - expected: '24.3310501', found: '12.1655251', error = '0.5000000'
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#586632 | #784. 旋转卡壳 | houbur | 97 | 283ms | 27844kb | C++20 | 1.5kb | 2024-09-24 14:47:11 | 2024-09-24 16:57:32 |
answer
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=5e5+5;
int n,m,top,xx,yy;
struct sb{
double x,y,k;
}e[N],st[N];
inline bool cmp(sb a,sb b){return (a.y==b.y)?(a.x<b.x):(a.y<b.y);}
inline double cross(sb a,sb b,sb c){return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline double ddd(sb a,sb b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline double dis(sb a,sb b,sb c){
double k=(b.y-c.y)/(b.x-c.x);
double bb=b.y-k*b.x;
return fabs(k*a.x-a.y+bb)/sqrt(k*k+1);
}
inline bool cmpp(sb a,sb b){
if(a.k!=b.k)return a.k<b.k;
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
signed main(){
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>e[i].x>>e[i].y;
sort(e+1,e+1+n,cmp);
st[++top]=e[1];
xx=st[top].x,yy=st[top].y;
for(int i=2;i<=n;i++)e[i].k=atan2(e[i].y-yy,e[i].x-xx);
sort(e+2,e+1+n,cmpp);
st[++top]=e[2];
for(int i=3;i<=n;i++){
while(top>1&&cross(st[top-1],st[top],e[i])<=0)top--;
st[++top]=e[i];
}st[++top]=st[1];
int l=1,r=1;
double ans=0;
for(l=1;l<top;l++){
int op=r;
while(dis(st[r%top+1],st[l+1],st[l])>=dis(st[r],st[l+1],st[l])){
r=r%top+1;
if(r==op){
ans=max({ans,ddd(st[r],st[l]),ddd(st[r],st[l+1])});
break;
}
}
ans=max({ans,ddd(st[r],st[l]),ddd(st[r],st[l+1])});
}
printf("%.7lf",ans);
return 0;
}/*10
0 0
100 -900
200 -1799
9800 -1799
9900 -900
10000 0
9999 100
9998 199
2 199
1 100
*/