P10590 Magnetic Blocks

On a vast and boundless plain, there are $N$ magnet stones scattered around. The properties of each magnet stone can be described by a 5-tuple $(x,y,m,p,r)$, where $x,y$ are its coordinates, $m$ is the mass of the stone, $p$ is the magnetic force, and $r$ is the attraction radius. If the distance between magnet stone $A$ and magnet stone $B$ is no greater than the attraction radius of $A$, and the mass of $B$ is no greater than the magnetic force of $A$, then $A$ can attract $B$. Xiaoqujiu brings his own magnet stone $L$ to the position $(x_0,y_0)$ on this plain, and we can treat the coordinates of magnet stone $L$ as $(x_0,y_0)$. Xiaoqujiu holds magnet stone $L$ and stays at the same place. All magnet stones that can be attracted by $L$ will be pulled over. At any moment, he may choose to switch to any magnet stone he has already obtained (which can also be the original magnet stone $L$) at $(x_0,y_0)$ to attract more magnet stones. Xiaoqujiu wants to know: at most how many magnet stones can he obtain?

The first line contains five integers $x_0,y_0,p_L,r_L,N$, representing Xiaoqujiu's position, the magnetic force and attraction radius of magnet stone $L$, and the number of scattered magnet stones on the plain. The next $N$ lines each contain five integers $x,y,m,p,r$, describing the properties of one magnet stone.

Output one integer, representing the maximum number of scattered magnet stones that can be obtained (not including the initially carried magnet stone $L$).

For $30\%$ of the testdata, $1 \le N \le 1000$. For another $30\%$ of the testdata, $p=r$. For $100\%$ of the testdata, $1 \le N \le 250000$, $-10^9 \le x,y \le 10^9$, $1 \le m,p,r \le 10^9$. Translated by ChatGPT 5