Submission #1795943

---

Source Code Expand

#include<iostream>
#include<iomanip>
#include<cmath>

int n;
int sx;
int sy;
int gx;
int gy;

int ff[200000];

int fff[200000];

const double cir=3.14159265358979*5;

//direc 1右 2左 4上 5下 から 差が1なら半周 それ以外なら4分の1周

bool judge(int xx,int yy){
    
    for(int i=0;i<n;i++){
        if(ff[i]==xx&&fff[i]==yy)
            return true;
    }
    
    return false;
}

double rec(int direc,int nx,int ny,double len){
    
    double res=300000000;
    
    if(len<abs(gx-sy)*100+abs(gy-sy)*100+200){
        
        if(nx==gx&&ny==gy)
            res=len;
        
        else{
            if(judge(nx,ny)){
                if(direc!=1)
                    if(nx<gx+1){
                        if(abs(direc-2)==1)
                            res=rec(2,nx+1,ny,len+90+cir*2)<res?rec(2,nx+1,ny,len+90+cir*2):res;
                        else
                            res=rec(2,nx+1,ny,len+90+cir)<res?rec(2,nx+1,ny,len+90+cir):res;
                    }
                if(direc!=2)
                    if(0<nx){
                        if(abs(direc-1)==1)
                            res=rec(1,nx-1,ny,len+90+cir*2)<res?rec(1,nx-1,ny,len+90+cir*2):res;
                        else
                            res=rec(1,nx-1,ny,len+90+cir)<res?rec(1,nx-1,ny,len+90+cir):res;
                    }
                if(direc!=4)
                    if(ny<gy+1){
                        if(abs(direc-5)==1)
                            res=rec(5,nx,ny+1,len+90+cir*2)<res?rec(5,nx,ny+1,len+90+cir*2):res;
                        else
                            res=rec(5,nx,ny+1,len+90+cir)<res?rec(5,nx,ny+1,len+90+cir):res;
                    }
                if(direc!=5)
                    if(0<ny){
                        if(abs(direc-4)==1)
                            res=rec(4,nx,ny-1,len+90+cir*2)<res?rec(4,nx,ny-1,len+90+cir*2):res;
                        else
                            res=rec(4,nx,ny-1,len+90+cir)<res?rec(4,nx,ny-1,len+90+cir):res;
                    }
            }
            else{
                if(direc!=1)
                    if(nx<gx+1){
                        if(!judge(nx+1,ny))
                            res=rec(2,nx+1,ny,len+100)<res?rec(2,nx+1,ny,len+100):res;
                        else
                            res=rec(2,nx+1,ny,len+90)<res?rec(2,nx+1,ny,len+90):res;
                    }
                if(direc!=2)
                    if(0<nx){
                        if(!judge(nx-1,ny))
                            res=rec(1,nx-1,ny,len+100)<res?rec(1,nx-1,ny,len+100):res;
                        else
                            res=rec(1,nx-1,ny,len+90)<res?rec(1,nx-1,ny,len+90):res;
                    }
                if(direc!=4)
                    if(ny<gy+1){
                        if(!judge(nx,ny+1))
                            res=rec(5,nx,ny+1,len+100)<res?rec(5,nx,ny+1,len+100):res;
                        else
                            res=rec(5,nx,ny+1,len+90)<res?rec(5,nx,ny+1,len+90):res;
                    }
                if(direc!=5)
                    if(0<ny){
                        if(!judge(nx,ny-1))
                            res=rec(4,nx,ny-1,len+100)<res?rec(4,nx,ny-1,len+100):res;
                        else
                            res=rec(4,nx,ny-1,len+90)<res?rec(4,nx,ny-1,len+90):res;
                    }
            }
        }
    }
    
    return res;
}

int main(){
    
    std::cin>>sx>>sy>>gx>>gy;
    
    std::cin>>n;
    
    for(int i=0;i<n;i++){
        std::cin>>ff[i]>>fff[i];
    }
    
    std::cout<<std::setprecision(18)<<rec(-1,sx,sy,0)<<std::endl;
    
    return 0;
}

Submission Info

Judge Result