P5544 [JSOI2016] Bomb Attack 1

JYY has recently become obsessed with a tower defense game. In the game, besides building structures, JYY can also use bombs to deal area damage to enemies on the screen.

The game map can be simply regarded as a two-dimensional plane. JYY has built $N$ buildings, and each building is a circle. The center of the $i$-th building is at $(x_i,y_i)$ with radius $r_i$. There are $M$ enemies on the map, and each enemy can be approximated as a point on the plane. The $i$-th enemy is located at $(p_i,q_i)$. JYY can use a bomb with an adjustable radius: he can set a radius not exceeding $R$, then choose a point on the plane to detonate it, and all enemies within the range are eliminated. Of course, because the bomb is very powerful, if the explosion range touches JYY's buildings, then JYY's buildings will be damaged. (Note: if the bomb's explosion range only touches the boundary of a building, it will not damage the building; if an enemy appears on the boundary of the explosion range, that enemy is eliminated.) JYY can freely control the detonation position and the explosion radius. As a cautious player, he wants to eliminate as many enemies as possible while ensuring that none of his buildings are damaged at all.

The first line contains three non-negative integers: $N, M, R$. The next $N$ lines each contain three integers. The $i$-th line gives $x_i,y_i,r_i$, describing the position and radius of the $i$-th building. The data guarantees that no buildings intersect (but their boundaries may touch). The next $M$ lines each contain two integers. The $i$-th line gives $p_i,q_i$, describing the position of the $i$-th enemy.

Output one line with one integer, representing the maximum number of enemies that JYY can eliminate.

- For $20\%$ of the data, $M = 2$. - For another $20\%$ of the data, $N = 0$. - For another $20\%$ of the data, $M \leq 50$. - For $100\%$ of the data, the Constraints are: - $0 \leq N \leq 10$. - $0 < M \leq 10^3$. - $1 \leq R, r_i \leq 2 \times 10^4$. - $|p_i|, |q_i|, |x_i|, |y_i| \leq 2 \times 10^4$. Translated by ChatGPT 5