QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#270503#7846. Glacier Travelandyc_03WA 2ms10152kbC++142.0kb2023-11-30 22:58:542023-11-30 22:58:55

Judging History

你现在查看的是最新测评结果

  • [2023-11-30 22:58:55]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10152kb
  • [2023-11-30 22:58:54]
  • 提交

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'