만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

직각삼각형의 동생은?

면접 대비

시간 제한3초메모리 제한1024 MB

요약
각 질의 (a, b)에 대해 꼭짓점이 (0, 0), (a, b), (a, 0)인 삼각형 안이나 경계 위에 있는 검은 점의 개수를 구합니다.
난이도

보통10점 중 6점

유형
기하, 정렬, 누적 합
정답자
아직 제출이 없습니다

문제

이 글에 깊은 감명을 받은 성우는 직각삼각형과 관련된 문제를 내기로 결심했다. 문제의 내용은 다음과 같다.

22차원 평면 위에 놓인 검은색 점이 NN개 주어진다. 이 점들의 xx좌표와 yy좌표는 모두 양수이다. 당신은 MM개의 질문에 각각 답해야 한다.

  • 각 질문마다 주어지는 점 (a_i,b_i)(a\_i, b\_i)에 대해, 점 (0,0)(0, 0), 점 (a_i,b_i)(a\_i, b\_i), 점 (a_i,0)(a\_i, 0)을 꼭짓점으로 갖는 삼각형 내부에 있는 검은색 점의 개수를 구해야 한다. 단, 삼각형의 경계에 놓인 점은 내부에 속하는 것으로 본다.

성우는 풀이를 생각하기 너무 귀찮아서 그만 잠들어 버렸다. 성우 대신 이 문제를 풀어주자!

입력

첫 번째 줄에 점의 개수 NN이 주어진다. (1≤N≤100 000)(1 \leq N \leq 100\, 000)

그 다음 NN개의 줄에는 각 검은색 점의 xx좌표와 yy좌표를 나타내는 두 정수 x_ix\_i, y_iy\_i가 공백을 사이에 두고 주어진다. 모든 검은색 점의 좌표는 서로 다르다. (1≤x_i,y_i≤109)(1 \leq x\_i, y\_i \leq 10^9)

그 다음 줄에 질문의 개수 MM이 주어진다. (1≤M≤100 000)(1 \leq M \leq 100\, 000)

그 다음 MM개의 줄에는 두 정수 a_ia\_i, b_ib\_i가 공백을 사이에 두고 주어진다. (1≤a_i,b_i≤109)(1 \leq a\_i, b\_i \leq 10^9)

출력

MM개의 줄에 걸쳐 각 질문에 대한 답을 출력한다. ii번째 줄에는 ii번째 질문에 대한 답을 출력한다.

예제1

  1. 예제 1

    입력
    3
    1 1
    1 2
    2 1
    3
    1 1
    2 4
    3 3
    
    예상 출력
    1
    3
    2