[백준] 25711번 인경산 (gold 5

import java.io.*;
import java.util.*;

class Point{
    double x;
    double y;
    double value;
    double reverseValue;
    public Point(double x, double y, double value,double reverseValue ){
        this.x=x;
        this.y=y;
        this.value=value;
        this.reverseValue=reverseValue;
    }
}
public class Main{
    public static void main(String[]args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int div=1000000;
        int n=Integer.parseInt(st.nextToken());
        int q=Integer.parseInt(st.nextToken());
        st=new StringTokenizer(br.readLine());
        StringTokenizer st2=new StringTokenizer(br.readLine());
        Point[] map=new Point[n+1];
        map[0]=new Point(0l,0l,0,0);
        map[1]=new Point(Double.parseDouble(st.nextToken())/div,Double.parseDouble(st2.nextToken())/div,0,0);
        for(int i=2; i<=n; i++){
            double x=Double.parseDouble(st.nextToken())/div;
            double y=Double.parseDouble(st2.nextToken())/div;
            double distance=Math.sqrt(Math.pow(x-map[i-1].x,2)+ Math.pow(y-map[i-1].y,2));
            double reverseValue;
            if(y>map[i-1].y){
                reverseValue=distance;
                distance*=3;
            }
            else if(y==map[i-1].y){
                distance*=2;
                reverseValue=distance;
            }
            else{
                reverseValue=distance*3;
            }

            map[i]=new Point(x,y,distance+map[i-1].value,reverseValue+map[i-1].reverseValue);
        }

        for(int i=0; i<q; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            if (start < end) {
                bw.write((map[end].value - map[start].value)*div + "\n");
            }
            else{
                bw.write((map[start].reverseValue - map[end].reverseValue)*div + "\n");
            }
        }
        bw.flush();
    }

}


//이문제에서 가장 오랜 시간이 걸린 부분은 소수점 표현이었다. 소수점 표현을 잘 안해본것도 있었고
//계속 예제2 케이스에서 소수점이 4.xxxxxxxxxx e9 와 같이 표현되었따.
//결론을 말하면, 위와같은 표현도 결국에 함축적으로 4.xxxxxx 10e9승으로 결국은
//똑같은 수를 나타내기에 정답처리가 되었다.

//여기서 크게 두가지를 깨달았는데 위처럼 똑같은 표현이라는 것
//만약 좀더 정밀하게 하고자하면, 위방법처럼 x,y에 일정수를 나누고 추후에 곱하여 설정하는것

//여기서 그냥 long으로 계산하면 10의 9승은 10의 18승이 되었다가, sqrt에서 다시 10의 9승이된다.
//이때 double은 모든 수 표현이가능하므로, 딱히 그수가 int 범위를 초과해도 상관없다. 단
//소수의 정밀도는 떨어지지만 말이다.
//문제에서 주어진대로 출력하면 되므로, string.format이나 System.out.printf("%.12f",(double 자료형));
//으로 출력하면됨

import java.io.*;
import java.util.*;

class Point{
    double x;
    double y;
    public Point(double x, double y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.valueOf(st.nextToken());
        int q=Integer.valueOf(st.nextToken());

        st=new StringTokenizer(br.readLine());
        StringTokenizer st2=new StringTokenizer(br.readLine());

        Point[] home=new Point[n+1];
        for(int i=1; i<=n; i++){
            home[i]=new Point(Double.valueOf(st.nextToken()) , Double.valueOf(st2.nextToken()));
        }

        double[] fd=new double[n+1]; //정방향
        double[] bd=new double[n+1]; //역방향

        for(int i=1; i<n; i++){
            int mul=com(home[i], home[i+1]);
            fd[i+1]=fd[i]+mul*Math.sqrt(Math.pow(home[i].x-home[i+1].x ,2 ) + Math.pow(home[i].y-home[i+1].y ,2));

        }

        for(int i=n; i>1; i--){
            int mul=com(home[i], home[i-1]);
            bd[i-1]=bd[i]+mul*Math.sqrt(Math.pow(home[i].x-home[i-1].x ,2 ) + Math.pow(home[i].y-home[i-1].y ,2));
        }

        for(int i=0; i<q; i++){
            st=new StringTokenizer(br.readLine());
            int s=Integer.valueOf(st.nextToken());
            int e=Integer.valueOf(st.nextToken());

            if(s==e){
                bw.write(0+"\n");
            }
            else if(s<e){
                bw.write((fd[e]-fd[s])+"\n");
            }
            else{
                bw.write((bd[e]-bd[s])+"\n");
            }
        }
        bw.flush();
    }
    public static int com(Point o1, Point o2){
        if(o1.y>o2.y){
            return 1;
        }
        else if(o2.y==o1.y){
            return 2;
        }
        else{
            return 3;
        }
    }

}


//2024 02 14에 작성한 코드. 실제로 long범위 초과 걱정안해도 double형에서 처리가 되어서 아무문제없음
//문제는 단순히 누적합+방법론에 gold5를 부여한 느낌.
//실수표현은 문제될 것이 없다.