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

Hitting the Targets

Hitting the Targets

A fundamental operation in computational geometry is determining whether two objects touch. For example, in a game that involves shooting, we want to determine if a player’s shot hits a target. A shot is a two dimensional point, and a target is a two dimensional enclosed area. A shot hits a target if it is inside the target. The boundary of a target is inside the target. Since it is possible for targets to overlap, we want to identify how many targets a shot hits. \includegraphics{https://static.e-olymp.com/content/32/324084febb59febed40588f9ad40edb4714c8966.jpg} The figure above illustrates the targets (large unfilled rectangles and circles) and shots (filled circles) of the sample input. The origin (\textbf{0}, \textbf{0}) is indicated by a small unfilled circle near the center. \InputFile Input starts with an integer \textbf{1} ≤ \textbf{m} ≤ \textbf{30} indicating the number of targets. Each of the next \textbf{m} lines begins with the word rectangle or circle and then a description of the target boundary. A rectangular target’s boundary is given as four integers \textbf{x_1} \textbf{y_1} \textbf{x_2} \textbf{y_2}, where \textbf{x_1} < \textbf{x_2} and \textbf{y_1} < \textbf{y_2}. The points (\textbf{x_1}, \textbf{y_1}) and (\textbf{x_2}, \textbf{y_2}) are the bottom-left and top-right corners of the rectangle, respectively. A circular target’s boundary is given as three integers \textbf{x y r}. The center of the circle is at (\textbf{x}, \textbf{y}) and the \textbf{0} < \textbf{r} ≤ \textbf{1000} is the radius of the circle. After the target descriptions is an integer \textbf{1} ≤ \textbf{n} ≤ \textbf{100} indicating the number of shots that follow. The next \textbf{n} lines each contain two integers \textbf{x y}, indicating the coordinates of a shot. All \textbf{x} and \textbf{y} coordinates for targets and shots are in the range \[\textbf{−1000}, \textbf{1000}\]. \OutputFile For each of the \textbf{n} shots, print the total number of targets the shot hits.
Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
3
rectangle 1 1 10 5
circle 5 0 8
rectangle -5 3 5 8
5
1 1
4 5
10 10
-10 -1
4 -3
Выходные данные #1
2
3
0
0
1
Источник 2012 ACM-ICPC North American Qualification Contest