QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#487754 | #784. 旋转卡壳 | mzmz001 | 0 | 1ms | 7980kb | C++14 | 1.2kb | 2024-07-23 09:30:59 | 2024-07-23 09:30:59 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,top1,top2,q1[500005],q2[500005],tb[500005],tot,md;
ll ans;
struct node{
ll x,y;
node operator - (const node &b)const{
return {x-b.x,y-b.y};
}
ll operator * (const node &b)const{
return x*b.y-y*b.x;
}
}p[500005];
bool cmp(node x,node y){
return x.x==y.x?x.y<y.y:x.x<y.x;
}
ll dis(node x,node y){
return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
int main(){
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld%lld",&p[i].x,&p[i].y);
sort(p+1,p+1+n,cmp);
for(ll i=1;i<=n;i++){
if(!(i<n&&p[i].x==p[i+1].x)){
while(top1>1&&(p[q1[top1]]-p[q1[top1-1]])*(p[i]-p[q1[top1]])>=0)top1--;
q1[++top1]=i;
}
if(!(i>1&&p[i].x==p[i-1].x)){
while(top2>1&&(p[q2[top2]]-p[q2[top2-1]])*(p[i]-p[q2[top2]])<=0)top2--;
q2[++top2]=i;
}
}
for(ll i=1;i<=top1;i++)tb[++tot]=q1[i];
md=tot;
if(q1[top1]!=q2[top2])tb[++tot]=q2[top2];
for(ll i=top2-1;i>1;i--)tb[++tot]=q2[i];
if(q1[1]!=q2[1])tb[++tot]=q2[1];
for(ll i=1,j=md;i<=md;i++){
while(j<tot&&(p[tb[i+1]]-p[tb[i]])*(p[tb[j]]-p[tb[j-1]])>=0)ans=max(ans,dis(p[tb[i]],p[tb[j]])),j++;
ans=max(ans,dis(p[tb[i]],p[tb[j]]));
}
printf("%lf",sqrt(ans));
}
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: 7980kb
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:
259552580.888447
result:
wrong answer 1st numbers differ - expected: '274339223.1895614', found: '259552580.8884470', error = '0.0538991'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%