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

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

근접 점의 개수

면접 대비

시간 제한1초메모리 제한128 MB

요약
각 쿼리마다 기준점을 제외하고 기준점에서 거리 d_v 안에 있는 점 개수를 셉니다.
난이도

쉬움10점 중 2점

유형
완전 탐색, 기하
정답자
아직 제출이 없습니다

문제

평면에 놓인 점이 여러 개 주어진다. 그중 한 점을 기준으로 삼아 그 점 가까이에 있는 점이 몇 개인지 세는 문제다.

점의 집합을 P={p1,p2,…,pn}P = \{p_1, p_2, \dots, p_n\}이라 하고, pip_i의 좌표를 (xi,yi)(x_i, y_i)라고 한다. 두 점 사이의 유클리드 거리는 d(pi,pj)d(p_i, p_j)로 나타낸다. d(pi,pj)≤dvd(p_i, p_j) \le d_v이면 점 pjp_j가 점 pip_i의 근접 범위에 있다고 하고, 이때 dvd_v를 근접 거리라고 부른다.

점의 집합 PP와 기준점 pip_i, 근접 거리 dvd_v가 주어질 때 pip_i의 근접 범위에 있는 점의 개수를 구하는 프로그램을 작성하시오. 기준점 pip_i 자신은 세지 않는다.

입력

첫째 줄에 점의 개수 nn이 주어진다 (2≤n≤10002 \le n \le 1000). 다음 nn개의 줄에는 각 점의 좌표 xix_i와 yiy_i가 정수로 주어진다 (−106≤xi,yi≤106-10^6 \le x_i, y_i \le 10^6).

그다음 줄에는 질의의 개수 tt가 주어진다 (1≤t≤501 \le t \le 50). 이어지는 tt개의 줄에는 각각 양의 정수 ii와 dvd_v가 주어지며 (1≤i≤n1 \le i \le n, 1≤dv≤1001 \le d_v \le 100), 기준점 pip_i와 그 근접 거리 dvd_v를 뜻한다.

출력

각 질의마다 기준점의 근접 범위에 있는 점의 개수를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    5
    0 0
    0 1
    1 1
    3 -3
    2 2
    3
    1 1
    5 3
    4 1
    
    예상 출력
    1
    3
    0