시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 417 | 138 | 93 | 41.704% |
정부는 오크 나무 숲을 통과하는 산책길를 만들려고 한다. 숲을 평면으로 나타낼 수 있고, 나무 N개는 평면위의 격자점으로 나타낼 수 있다.
산책길은 축에 평행한 직사각형으로 나타낸다. 산책길의 변 위에 있는 나무는 베어내야 한다. 산책길 내부에 있는 나무는 문제가 되지 않으며, 베어내지 않아도 된다.
산림청에서는 산책길 계획을 공모전으로 열었고, 총 P개의 산책길가 접수되었다. 각각의 접수된 산책길에 대해서, 그 산책길를 만들려면 나무를 몇 개나 잘라내야하는지 구하는 프로그램을 작성하시오. 나무는 변 위에 있는 나무만 베어야한다.
첫째 줄에 나무의 수 N이 주어진다. (1 ≤ N ≤ 300,000)
다음 N개 줄에는 나무의 좌표 X와 Y가 한 줄에 하나씩 주어진다. 한 점위에 나무가 두 개 이상 있는 경우는 없다. (1 ≤ X, Y ≤ 109)
다음 줄에는 접수된 산책로 계획의 수 P (1 ≤ P ≤ 100,000)가 주어진다.
다음 P개 줄에는 X1, Y1, X2, Y2 (1 ≤ X1 < X2 ≤ 109, 1 ≤ Y1 < Y2 ≤ 109)가 주어진다. (X1, Y1)은 직사각형의 왼쪽 아래 좌표, (X2, Y2)는 오른쪽 위 좌표를 나타낸다.
총 P개의 줄에 각 산책로를 건설하려면 나무를 몇 개나 베어야 하는지 출력한다. 입력으로 주어진 순서를 지켜 출력한다.
6 1 2 3 2 2 3 2 5 4 4 6 3 4 2 2 4 4 2 2 6 5 3 3 5 6 5 1 6 6
3 4 0 1