P15836 [The 1st Lanqiao Cup International Contest] Fishing Master

Xiaoming is playing a fishing game on a plane. There are $n$ fish on the plane, and the coordinates of the $i$-th fish are $(x_i, y_i)$. At each moment, Xiaoming may choose one fish that is still on the plane and cast a net at its position. That fish will be caught in the net, and at the same time, all fish whose (Euclidean) distance to that fish is no more than $R$ will also be caught in the net. The caught fish are taken away by Xiaoming and disappear from the plane. Note that Xiaoming can only choose a fish that is still on the plane (not yet taken away) to cast the net. If there are no fish, he cannot cast the net. Xiaoming wants to know the minimum number of net casts needed to catch all fish. Hint: The Euclidean distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$.

The first line contains two integers $n, R$, representing the number of fish and the catching distance of the net. The next $n$ lines each contain two integers, representing the coordinates of a fish.

Output one line containing one integer, representing the minimum number of net casts.

### Constraints For $20\%$ of the testdata, $1 \le n \le 8$. For $40\%$ of the testdata, $1 \le n \le 12$. For $60\%$ of the testdata, $1 \le n \le 25$. For the remaining $40\%$ of the testdata, $1 \le n \le 50$. The fish positions are generated using a random function and are uniformly distributed on the plane. For all testdata, $|x_i|, |y_i| \le 1000$, and $R \le 2000$. Translated by ChatGPT 5