P3737 [HAOI2014] Remote Sensing Monitoring

Aliens are intelligent life beyond Earth. Whether aliens look like humans is not important, but at least they should fit our current understanding of basic life forms. For example, every life form we know depends on liquid water and is composed of complex organisms based on organic molecules of the chemical element carbon (C). Astronomers at the ZDM Laboratory have persistently observed the planet ZDM-99 for more than ten years. This red planet, nicknamed the “War God,” fascinates them. Over the years, they have made many exciting discoveries. The surface of ZDM-99 shows obvious variations in brightness. After years of detailed study and mapping, astronomers have concluded that the dark regions are land, while the bright regions are lakes and oceans. They firmly believe that where there is water, there must be traces of life. The observing conditions on this night were unprecedentedly good. ZDM-99 was very bright, and several laser points appeared from time to time. The astronomers inferred that these laser points were very likely signs of intelligent life beyond Earth. Unfortunately, the laser points disappeared after only a short time. The radio telescopes of the ZDM Laboratory can each remotely sense a circular region with radius $R$. To detect all laser points simultaneously, the laboratory plans to install multiple radio telescopes along a single horizontal straight line. Assume this horizontal line for placing radio telescopes is the $x$-axis. The laser points on ZDM-99 are located at $P_1(x_1, y_1), P_2(x_2, y_2), \cdots, P_n(x_n, y_n)$ (ignore the $z$ coordinate).  The astronomers at the ZDM Laboratory want to know the minimum number of radio telescopes needed to detect all the laser points.

The first line contains $N, R$, denoting the number of laser points and the detection radius of a radio telescope. Lines $2$ to $N+1$ contain $X_i, Y_i$, the coordinates of the $i$-th laser point.

Output a single line: the minimum number of radio telescopes required.

Constraints: $1 \le R \le 50$, $1 \le N \le 100$, $-1000 \le X_i, Y_i \le 1000$, $|Y_i| \le R$. All inputs are guaranteed to be integers. Translated by ChatGPT 5