Problem:
The village consists of n houses located along a straight road. The coordinate of the i-th house is x[i].The internet provider wants to install several Wi-Fi access points in the village, covering all houses. A point with coverage radius r costs A + B.( R )^2. Find the minimum cost of the required access points.
Help of any kind is absolutely thankful!
What are the inputs and constraints?
Can’t we solve this problem using binary search, as the cost function is a monotonic increasing function. We can first sort the array and then start from the middle for a random r as range is circular then starting from middle element seems a better choice. Then we can use two pointer to move left and right side of the middle element.