시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 65 | 20 | 18 | 28.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까지 허용한다.
4 2 1 4 2 3 0 1 1 1 1 4 3 4
5.0000000 1.0000000
첫 번째 쿼리의 경우에는 (1.5, 2.5)에 모이는 것이 최소이고, 두 번째 쿼리의 경우에는 (1, 1)에 모이는 것이 최소이다.