我正在试图解决以下问题，这是编程竞赛的一部分：
问题ID:CIELLAND
奇尔厨师用她的餐馆开发了一个新岛屿在岛上，CIEL打算建造N家餐厅，而第三家餐厅的座席将是（西，彝）。此外，ciel将创建k条道路，其位置尚未确定。每条路必须是无限长的直线。
设di为i-th餐厅与i-th餐厅最近道路之间的距离。ciel希望创建k条最大值（d1，d2，…，dn）最小的道路。您的任务是计算max（d1，d2，…，dn）的最小值。
关于我该怎么做有什么想法吗另外，竞赛的社论已经出炉（http://www.codechef.com/wiki/march-2012-cook-problem-editorials），但我无法理解解决方案。
我们非常感谢您对我们将采取的方法提供帮助。
最佳答案
在高层，他们正在重新制定问题，以便更容易解决。通过在下面的光线中投射，它们限制了可能要考虑的线的数量。
问题A：有N个圆圈。第i个圆的中心是（XI），
所有的圆都有半径，我们可以画X线
任何圆与至少一条线相交最小值是多少
X？
为了进一步解释，让我们用一个词来重新表述这个问题：餐馆是规则的黏附者，有一条规则说所有的餐馆都必须在离道路最大的距离上达成一致——这将是R。餐厅所创建的圈子和R代表一条线需要相交的地方来满足这一要求。新问题要求最少的道路数量来完成这项工作。
如果这在K路下是不可能的，那就必须有所改变我们不能为原始问题添加道路，但我们可以修改r。这是二进制搜索的地方，但我们必须首先解决问题a。
现在，让我们考虑解决问题A。首先，行可以是
仅限于两个圆的公共切线因为如果一条线
与一些（至少2个）圆相交，我们可以这样移动直线
移动的线与相同的圆相交，并且移动的线
是常见的切线之一。如果一条线相交少于两个圆，
这是无用的（但要小心N=1的情况）最多有4个
两个圆的公共切线，所以我们最多考虑2条
*N*（N-1）行。
重要的是，我们需要找到与多个圆相交的线。每对圆最多四行，检查源代码是否实现。
下一个重要的步骤是动态编程，找到覆盖所有圆的最小行数“mask”是一个位掩码，指示在考虑每一行时哪些圆被击中。
这解决了问题，但现在我们必须转换回来还记得R吗我们现在可以用二元搜索来找到最小的r，使得x希望这有帮助，棘手，但有趣的问题。
关于algorithm - 与二进制搜索有关的编程难题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9785302/