P2504 [HAOI2006] Smart Monkey

A troop of monkeys lives in a tropical rainforest and feeds on fruit from the trees. After heavy rain yesterday, the sky has cleared, but the forest floor is still flooded, with only parts of the tree canopies above the water. Monkeys cannot swim, but they are good jumpers, so they can still move among the exposed canopies to find the fruit they like to eat. There are $N$ trees whose canopies are above the water. Assume each tree’s own diameter is negligible. We set up a Cartesian coordinate system on this area, and each tree’s position is represented by its coordinate (no two trees share the same coordinate). There are $M$ monkeys living in this area. During the rain, they hid in dense, tall canopies and were not swept away. Because of differences in age and physical fitness, their jumping abilities differ. Some monkeys can jump farther (they can also jump to closer trees), while others can only jump shorter distances. These monkeys are very smart: by visual judgment, they can accurately decide whether they can jump to another tree. Given the number of monkeys and each monkey’s maximum jump distance, as well as the coordinates of all exposed trees, your task is to count how many monkeys can forage on all the exposed tree canopies in this area.

The input includes: - The first line contains an integer $M$ $(2 \le M \le 500)$, the number of monkeys. - The second line contains $M$ integers, the maximum jump distance of each monkey (each integer is in $1 \sim 1000$). - The third line contains an integer $N$ $(2 \le N \le 1000)$, the total number of trees. - Lines $4$ to $N+3$ contain the coordinates of the $N$ trees (both coordinates are integers in the range $-1000 \sim 1000$). (Integers on the same line are separated by spaces.)

Output a single integer: the number of monkeys that can forage on all canopies in this area.

For $40\%$ of the testdata, it is guaranteed that $2 \le N \le 100$, $1 \le M \le 100$. For all the testdata, it is guaranteed that $2 \le N \le 1000$, $1 \le M \le 500$. Thanks to @charlie003 for correcting the testdata. Translated by ChatGPT 5