만드는 중입니다

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

원 안의 점 개수 쿼리

시간 제한8초메모리 제한512 MB

요약
고정된 N개의 점에 대해 M개의 원 질의가 주어질 때, 각 원 안이나 원주 위에 있는 점의 개수를 세어 출력한다.
난이도

어려움10점 중 9점

유형
기하, 분할 정복, 정렬, 시뮬레이션
정답자
아직 제출이 없습니다

문제

2차원 좌표 평면에 점 NN개가 놓여 있다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

  • x y r: 중심이 (x,y)(x, y)이고 반지름이 rr인 원의 내부에 있는 점의 개수를 출력한다. 원의 둘레 위에 있는 점도 내부에 있는 점으로 센다.

즉, 점 (a,b)(a, b)는 (a−x)2+(b−y)2≤r2(a - x)^2 + (b - y)^2 \le r^2을 만족할 때 답에 포함된다.

같은 좌표에 점이 둘 이상 놓여 있을 수 있고, 이때는 겹친 점을 모두 따로 센다. 쿼리는 점을 추가하거나 지우지 않으므로 처리 순서가 답에 영향을 주지 않는다.

입력

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

둘째 줄부터 NN개의 줄에 각 점의 좌표 xx와 yy가 공백으로 구분되어 주어진다 (0≤x,y≤1 000 0000 \le x, y \le 1\,000\,000).

다음 줄에 쿼리의 개수 MM (1≤M≤100 0001 \le M \le 100\,000)이 주어진다.

다음 MM개의 줄에 쿼리 정보 xx, yy, rr이 공백으로 구분되어 주어진다 (0≤x,y≤1 000 0000 \le x, y \le 1\,000\,000, 1≤r≤1 000 0001 \le r \le 1\,000\,000).

입력으로 주어지는 모든 수는 정수다.

출력

쿼리마다 원 안에 있는 점의 개수를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.

예제3

  1. 예제 1

    입력
    5
    5 9
    2 7
    9 5
    5 10
    6 10
    10
    5 3 4
    4 3 2
    8 9 4
    1 10 4
    8 2 2
    3 8 2
    1 9 3
    7 2 3
    10 4 3
    6 5 2
    
    예상 출력
    0
    0
    3
    2
    0
    1
    1
    0
    1
    0
    
  2. 예제 2

    입력
    1
    3 4
    3
    0 0 5
    0 0 4
    3 4 1
    
    예상 출력
    1
    0
    1
    
  3. 예제 3

    입력
    4
    0 0
    0 10
    10 0
    10 10
    4
    5 5 7
    5 5 8
    0 0 10
    5 5 1
    
    예상 출력
    0
    4
    3
    0