QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#270503 | #7846. Glacier Travel | andyc_03 | WA | 2ms | 10152kb | C++14 | 2.0kb | 2023-11-30 22:58:54 | 2023-11-30 22:58:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
typedef long double db;
const db eps=1e-9;
struct ques{
db ti;int ty,x;
}p[2*N];db dis[N];
int X[N],Y[N];
bool cmp(ques n1,ques n2) {
if(n1.ti==n2.ti) return (n1.ty<n2.ty);
return (n1.ti+eps<n2.ti);
}
db doit(db A,db B,db C,db X){
return sqrt(A*X*X+B*X+C);
}
int main()
{
db s;scanf("%Lf",&s);
int n;scanf("%d",&n);
X[0]=Y[0]=0;
for(int i=1;i<=n;i++) scanf("%d%d",&X[i],&Y[i]);
dis[0]=0;
for(int i=1;i<=n;i++){
dis[i]=dis[i-1]+sqrt((X[i]-X[i-1])*1.0*(X[i]-X[i-1])+(Y[i]-Y[i-1])*1.0*(Y[i]-Y[i-1]));
}
int tot=0;
for(int i=1;i<=n;i++){
p[++tot].ty=0;p[tot].ti=dis[i];p[tot].x=i;
p[++tot].ty=1,p[tot].ti=dis[i]-s,p[tot].x=i;
}
sort(p+1,p+tot+1,cmp);
db t1,t2,t3,t4,t5,t6,t7,t8,Ans=1e9;
for(int i=1;i<=tot;i++){
if(p[i].x==n) break;
if(p[i].ty==0){
t1=(X[p[i].x+1]-X[p[i].x])/(dis[p[i].x+1]-dis[p[i].x]);
t2=X[p[i].x]-t1*p[i].ti;
t3=(Y[p[i].x+1]-Y[p[i].x])/(dis[p[i].x+1]-dis[p[i].x]);
t4=Y[p[i].x]-t3*p[i].ti;
}
else{
t5=(X[p[i].x+1]-X[p[i].x])/(dis[p[i].x+1]-dis[p[i].x]);
t6=X[p[i].x]-t5*p[i].ti;
t7=(Y[p[i].x+1]-Y[p[i].x])/(dis[p[i].x+1]-dis[p[i].x]);
t8=Y[p[i].x]-t7*p[i].ti;
}
assert((dis[p[i].x+1]-dis[p[i].x])>1e-6);
if(p[i].ti<-eps) continue;
db tmp1=t5-t1,tmp2=t6-t2,tmp3=t7-t3,tmp4=t8-t4;
db A=tmp1*tmp1+tmp3*tmp3,C=tmp2*tmp2+tmp4*tmp4,B=2*(tmp1*tmp2+tmp3*tmp4);
db Mid=-B/(2*A);
if(fabs(A)<eps){
if(B<-eps) Mid=1e18;
else Mid=-1e18;
}
if(Mid>=p[i].ti&&Mid<=p[i+1].ti) Ans=min(Ans,doit(A,B,C,Mid));
else if(Mid<p[i].ti) Ans=min(Ans,doit(A,B,C,p[i].ti));
else Ans=min(Ans,doit(A,B,C,p[i+1].ti));
}
printf("%.9Lf\n",Ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10128kb
input:
5 4 20 0 10 0 10 10 0 10
output:
3.535533906
result:
ok found '3.53553', expected '3.53553', error '0.00000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 10068kb
input:
3.16227766 9 -2 4 2 4 3 1 4 4 5 1 6 4 10 2 6 1 7 4
output:
1.000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 10092kb
input:
20 5 9 38 36 16 -5 36 -24 15 30 37
output:
2.293595760
result:
ok found '2.29360', expected '2.29360', error '0.00000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 10080kb
input:
10 40 17 18 12 -5 12 -16 -10 16 7 -15 18 -18 19 15 -19 1 -18 11 -8 -12 -17 -12 5 -12 -15 -8 -10 -10 -4 4 -2 -3 15 17 -2 -9 -13 7 -12 17 15 -3 -19 -14 6 6 14 -5 -10 -15 17 -16 -11 15 9 -6 10 8 19 -1 12 -6 -18 2 14 17 9 -7 -8 -3 7 11 -12 -14 -19 4 -1 15 -17 16
output:
0.000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 10076kb
input:
10 40 10 11 11 15 6 -16 -18 4 10 10 -10 16 -17 11 2 6 -6 -9 17 -7 -7 -5 10 -18 -9 9 -14 10 19 -3 -14 -3 15 -5 -3 16 -10 14 -9 -12 10 -18 10 -4 -9 -11 11 -2 9 2 12 15 2 -17 -8 -16 19 7 -19 -2 -17 7 16 -9 6 -6 8 -18 15 9 17 2 -19 12 -15 -9 1 -15 19 -12
output:
0.344214437
result:
ok found '0.34421', expected '0.34421', error '0.00000'
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 10152kb
input:
1000 4000 -720538 -681604 667325 347504 -911397 -962007 -264075 -858319 49605 149209 964851 361021 -397274 28661 -460607 -273701 104862 -136807 -803899 -693703 -974 -337735 323678 -209811 -745617 -358684 -984333 603546 722843 -444579 701511 -255784 -676477 -836480 998942 -227888 -502059 -438394 9641...
output:
0.000000000
result:
wrong answer 1st numbers differ - expected: '0.04450', found: '0.00000', error = '0.04450'