Mineral deposits

문제

You handle signal processing for an extra-terrestrial mining company, and your vessel is currently approaching an asteroid. Preliminary scans show the presence of $kk$ mineral deposits on the asteroid, but their precise locations are unknown.

The surface of the asteroid can be seen as a grid of integer coordinates. Each of the mineral deposits is located at unknown integer coordinates such that the $ii$th deposit has coordinates $(x_i,y_i)(x\_i,\; y\_i)$ with $-b\le x_i\le b-b\; \backslash le\; x\_i\; \backslash le\; b$ and $-b\le y_i\le b-b\backslash le\; y\_i\; \backslash le\; b$ for some integer $bb$ corresponding to the size of your initial scan.

To determine the precise locations of the mineral deposits, you may send probes to the surface of the asteroid. The probes are sent out in waves of several probes at once.

Say you sent a wave of $dd$ probes to the surface at coordinates $(s_j,t_j)(s\_j,t\_j)$ for $1\le j\le d1\backslash leq\; j\backslash leq\; d$. When a probe arrives at its coordinates, it determines the Manhattan distances to each of the $kk$ mineral deposits and sends the distances back to the ship. All data packets arrive at the same time, and it is not possible to determine which probes returned which distances. Thus the wave returns the $k\cdot dk\backslash cdot\; d$ integer distances \[|x_i-s_j| + |y_i - t_j| \qquad\text{for all } i \in \{1,\ldots,k\} \text{ and } j \in\{ 1,\ldots,d\}\,.\]

You need to minimise the number of waves of probes that is sent to the surface.