Submission #1775773

---

Source Code Expand

#include<iostream>
#include"math.h"

int n,start,goal;

int l[200000],r[200000];

float rec(int x,int y,float num){
    
    float res;
    
    //ゴールへ(単数)
    res=num+sqrt((goal-x)*(goal-x)+(n-y)*(n-y));
    
    //ゴールへ(複数)
    for(int i=1;i<=n-y-1;i++)
        if(l[y+i]<=(float)(goal-x)*i/(n-y)&&(float)(goal-x)*i/(n-y)<=r[y+i])
            res=res<num+sqrt((goal-x)*(goal-x)+(n-y)*(n-y))?res:num+sqrt((goal-x)*(goal-x)+(n-y)*(n-y));
    
    //一つ次
    if(y<n){
        res=
        res<rec(l[y+1],y+1,num+sqrt((l[y+1]-x)*(l[y+1]-x)+1))?
    res:rec(l[y+1],y+1,num+sqrt((l[y+1]-x)*(l[y+1]-x)+1));
        
        res=
        res<rec(r[y+1],y+1,num+sqrt((r[y+1]-x)*(r[y+1]-x)+1))?
    res:rec(r[y+1],y+1,num+sqrt((r[y+1]-x)*(r[y+1]-x)+1));
    }
    
    //複数次
    for(int i=2;i<=n-y;i++){
        for(int j=1;j<=i-1;j++){
            if(l[y+i]<=(float)(l[y+i]-x)*j/i&&(float)(l[y+i]-x)*j/i<=r[y+i])
                res=res<rec(l[y+i],y+i,num+sqrt((l[y+i]-x)*(l[y+i]-x)+i*i))?
                res:rec(l[y+i],y+i,num+sqrt((l[y+i]-x)*(l[y+i]-x)+i*i));
            
            if(l[y+i]<=(float)(r[y+i]-x)*j/i&&(float)(r[y+i]-x)*j/i<=r[y+i])
                res=res<rec(r[y+i],y+i,num+sqrt((r[y+i]-x)*(r[y+i]-x)+i*i))?
                res:rec(r[y+i],y+i,num+sqrt((r[y+i]-x)*(r[y+i]-x)+i*i));
        }
    }
    
    return res;
    
}

int main(){
    
    std::cin>>n>>start>>goal;
    
    for(int i=0;i<n+1;i++)
        std::cin>>l[n]>>r[n];
    
    std::cout<<rec(start,0,0)<<std::endl;
    
    return 0;
}

Submission Info

Judge Result