시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB65201828.571%

문제

N명의 사람들이 2차원 평면 위에 서있다. 사람의 번호는 1번부터 N번까지 번호가 매겨져 있다. 이때, 다음 쿼리의 정답을 구하는 프로그램을 작성하시오.

  • l r: l번 사람부터 r번 사람까지 한 점 P에 모일 때, 각 사람과 점 P사이의 거리의 합의 최솟값을 출력한다.

두 점 (x1, y1), (x2, y2) 사이의 거리는 max(|x1-x2|, |y1-y2|)로 구한다.

입력

첫째 줄에 사람의 수 N과 쿼리의 수 Q (1 ≤ N, Q ≤ 100,000)

둘째 줄부터 N개의 줄에 사람의 좌표 Xi, Yi가 공백으로 구분해서 주어진다. (-1,000,000,000 ≤ Xi, Yi ≤ 1,000,000,000)

다음 Q개의 줄에는 쿼리 Li, Ri가 공백으로 구분해서 주어진다. (1 ≤ Li ≤ Ri ≤ N)

출력

각각의 쿼리마다 정답을 출력한다. 정답과의 절대/상대 오차는 10-3까지 허용한다.

예제 입력 1

4 2
1 4
2 3
0 1
1 1
1 4
3 4

예제 출력 1

5.0000000
1.0000000

힌트

첫 번째 쿼리의 경우에는 (1.5, 2.5)에 모이는 것이 최소이고, 두 번째 쿼리의 경우에는 (1, 1)에 모이는 것이 최소이다. 

출처