c++ - Does anyone know how to solve this problem - the minimum number of base stations to be built between villages?

Question

I feel like my thinking is too simple. My idea is to divide the distance between villages by 2R

Answer 1

Your answer is definitely wrong. A simple example is that there are only two villages separated by a long distance, then the distance /2R will be very large. In fact, two base stations are enough.
This question can be greedy. You sort the villages by the abscissa. If you consider the leftmost village, it must be covered. Then obviously, it is best to build a village within R distance to the right of it (not only does it cover He, and as far to the right as possible, can cover as many other villages as possible)
In this way, the first base station is built, he covers some villages, and continues to repeat the above operations for the remaining villages That’s it.