eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Vicinity

Vicinity

This is one of the most basic geometry proximity problems. We are given \textbf{n} points in the plane and we should determine which points are \textit{in the vicinity} of a particular point. Let the set of points \textbf{P = \{p_1, p_2 , …, p_n\}}, where \textbf{p_i} has coordinates \textbf{(x_i, y_i)}. We use \textbf{d(p_i, p_j)} to denote the distance between the two points. A point \textbf{p_j} is \textit{in the vicinity} of point \textbf{p_i} if \textbf{d(p_i, p_j)} ≤ \textbf{d_v}. We may call \textbf{d_v} the vicinity distance. Given a set of points \textbf{P}, point \textbf{p_i} and \textbf{d_v}, your task is to write a program to calculate the number of points which are in the vicinity of point \textbf{p_i}. \InputFile The first line contains an integer \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{1000}) which determines the number of points. The following \textbf{n} lines contain two integers which correspond to the coordinates (\textbf{x_i}, \textbf{y_i}) of each point (\textbf{-10^6} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{10^6}). Then, the following line includes \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{50}) indicating the number of test cases, followed by \textbf{t} lines and each line contains \textbf{2} positive integers \textbf{i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}) and \textbf{d_v} (\textbf{1} ≤ \textbf{d_v} ≤ \textbf{100}) which indicate the point \textbf{p_i} and its vicinity distance, respectively. \OutputFile For each test case, print out in a line the number of points in the vicinity of the corresponding point.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
5
0 0
0 1
1 1
3 -3
2 2
3
1 1
5 3
4 1
Выходные данные #1
1
3
0
Источник ACM-ICPC Asia Phuket Regional Programming Contest 2013, Practice Session, 21 November 2013