Submission #1775801

---

Source Code Expand

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

float dp[200000][2];

int n,start,goal;

int l[200000],r[200000];

float rec(int x,int y,float num){
    
    float res=10000000;
    
    int ju=-1;
    
    if(l[y]==x)ju=0;
    
    if(r[y]==x)ju=1;
    
    if(ju!=-1){
    if(dp[y][ju]==-1){
    
    //ゴールへ(単数)
    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));
        }
    }
        dp[y][ju]=res;
    }
    else
        res=dp[y][ju];
    }
    
    if(ju==-1){
        //ゴールへ(単数)
        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(){
    
    for(int i=0;i<200000;i++)
        for(int j=0;j<2;j++)
            dp[i][j]=-1;
    
    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