QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#487724 | #784. 旋转卡壳 | mzmz001 | 0 | 1ms | 8060kb | C++14 | 1.2kb | 2024-07-23 08:15:07 | 2024-07-23 08:15:07 |
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;
}p[500005];
bool cmp(node x,node y){
return x.x==y.x?x.y<y.y:x.x<y.x;
}
ll dx(ll x,ll y){
return p[x].x-p[y].x;
}
ll dy(ll x,ll y){
return p[x].y-p[y].y;
}
ll get_d(ll x,ll y){
return dx(x,y)*dx(x,y)+dy(x,y)*dy(x,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&&dy(q1[top1],q1[top1-1])*dx(i,q1[top1])<dy(i,q1[top1])*dx(q1[top1],q1[top1-1]))top1--;
q1[++top1]=i;
}
if(!(i>1&&p[i].x==p[i-1].x)){
while(top2>1&&dy(q2[top2],q2[top2-1])*dx(i,q2[top2])>dy(i,q2[top2])*dx(q2[top2],q2[top2-1]))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&&dy(tb[i+1],tb[i])*dx(tb[j],tb[j+1])<dy(tb[j],tb[j+1])*dx(tb[i+1],tb[i]))j++;
ans=max(ans,get_d(tb[i],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: 10
Accepted
time: 1ms
memory: 8056kb
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:
274339223.189561
result:
ok found '274339223.1895610', expected '274339223.1895614', error '0.0000000'
Test #2:
score: 10
Accepted
time: 1ms
memory: 8056kb
input:
1000 0 0 -887614 -1937 -1459359 -3808 -2421409 -24096 -3273181 -48456 -3917594 -76664 -4402753 -100164 -5375022 -150897 -5993935 -192089 -6587159 -238825 -7549680 -333298 -8330993 -416479 -9244392 -515027 -10010900 -598589 -10374584 -640275 -10767641 -686907 -11173081 -741316 -11821952 -833327 -1260...
output:
262687047.927491
result:
ok found '262687047.9274910', expected '262687047.9274906', error '0.0000000'
Test #3:
score: 10
Accepted
time: 1ms
memory: 8060kb
input:
1000 0 0 -631055 -2758 -1328409 -7463 -2248672 -20536 -2412978 -23564 -2659543 -28441 -3383179 -43406 -4183375 -64326 -4856658 -88337 -5799682 -134822 -6757348 -189404 -7132846 -212164 -7563226 -242116 -8368716 -300012 -9321463 -381770 -9831821 -432746 -10409503 -491057 -11360852 -607259 -11874199 -...
output:
257868038.643590
result:
ok found '257868038.6435900', expected '257868038.6435897', error '0.0000000'
Test #4:
score: 10
Accepted
time: 1ms
memory: 8036kb
input:
1000 0 0 -48652 -588 -951356 -20091 -1517426 -33325 -1965414 -51971 -2466111 -74904 -3046762 -103888 -3555833 -132002 -3976901 -156059 -4972848 -245498 -5921476 -332492 -6353035 -375491 -7327511 -496188 -7939064 -575429 -8842272 -694656 -9246222 -756797 -9771758 -860630 -10633761 -1031205 -10981774 ...
output:
259539672.480453
result:
ok found '259539672.4804530', expected '259539672.4804534', error '0.0000000'
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 7984kb
input:
1000 0 0 -456569 -2668 -1141521 -7887 -1270801 -8967 -1971135 -21206 -2919889 -38188 -3903859 -71231 -4752603 -107450 -5508682 -143873 -6214620 -183392 -6718977 -212193 -7452291 -271600 -8408796 -354998 -9261882 -432674 -9528618 -457608 -10099091 -513153 -10320120 -535958 -11067358 -614356 -12050731...
output:
250213042.785528
result:
wrong answer 1st numbers differ - expected: '250217366.4826218', found: '250213042.7855280', error = '0.0000173'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%