아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

직각삼각형의 동생은?

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

요약
각 질의점에 대해 세 꼭짓점이 (0,0), (a,b), (a,0)인 직각삼각형 내부(경계 포함)에 들어가는 주어진 점의 개수를 구한다.
난이도

보통10점 중 7점

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

문제

직각삼각형의 동생은 직각삼각이다!

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

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