编程的难题，我想解决以下问题这是一个程序设计大赛的一部分：与二进制搜索
问题ID：CIELLAND
厨师Ciel的发展与她的餐馆一个新的岛屿。在岛上，Ciel打算建立N家餐馆，第i家餐厅的坐标为（xi，yi）。此外，Ciel将创建K路，其位置尚未确定。每条道路必须是无限长的直线。
让di是第i家餐厅和最近的餐厅之间的距离。 Ciel希望创建最小化max（d1，d2，...，dN）的K道路。你的任务是计算max（d1，d2，...，dN）的最小值。
任何想法，我应该如何处理它？此外，比赛编辑出局（http://www.codechef.com/wiki/march-2012-cook-problem-editorials），但我不明白的解决方案。
任何关于要遵循的方法的帮助将不胜感激。
在高层次上，他们正在重新解决问题，以便更容易解决问题。通过投射在下面的光线，他们限制了可能的线路数量。
问题A：有N个圆圈。第i个圆的中心是（xi， yi）并且所有的圆都有半径R.让我们可以画出X行，例如 任何圆与至少一条直线相交。什么是最小的 X？
为了进一步解释，让我们用言语改写问题A：餐厅是规则的坚持者，并且有一条规则规定所有餐馆必须同意距离道路的最大距离 - 这将是R.由餐厅和R创建的圆代表线需要相交以满足此要求的地方。新问题要求最少数量的道路来做到这一点。
如果这在K道路下是不可能的，那么一定要改变。我们不能根据原始问题添加道路，但是我们可以修改R.这是二进制搜索的来源，但我们必须首先解决问题A.
现在，让我们考虑解决问题A.首先，行可以是 限于两个圆的共同切线。因为如果一条线 与一些（至少2个）圆相交，我们可以移动线如 ，移动的线与相同的圆相交，并且移动的线 是常用切线之一。如果一条线相交少于2个圆，则它是无用的（但要注意N = 1的情况）。最多有两条线与两个圆相切，所以我们最多考虑2条线，即N *（N-1）行。
重要的是这个，我们需要找到与多个圆相交的直线。每对圆圈最多需要考虑四行，请查看源代码的实现。
接下来的一大步是找到覆盖所有圈子的最少行数的动态规划。'mask'是一个位掩码，指示在考虑每条线时哪些圆圈已经被击中。
这解决了这个问题，但现在我们必须转换回来。记得R？我们现在可以进行二分搜索以找到最小R，使得X < = K。根据我对问题A的重新定义，其所有餐厅都会同意并保持最小距离
希望帮助，棘手但有趣的问题。
“重要的部分是这样的，我们需要找到相交多于一个圆的线，每个圆最多需要考虑四条线”。我很抱歉，但我没有完全明白。我认为你说线需要交叉多于一个圆，否则线不会给我们所需的最小线。我对吗 ？为什么从每一对考虑最多4条线呢？ – arya 2012-03-21 06:17:46
除非只有一个城市，否则我们需要一条线来至少交两圈。如果一条直线与一个圆相交，则不值得考虑该直线，因为还有一些其他圆可以相交并且仍然与该直线相交。如果这更容易，可以把它看成两点 - 总是有一条线与两点相交。 4条线是由两个圆的共同切线组成的线。你可以尝试证明这个数字不超过4，这对我来说很难在没有绘制的情况下进行。 – dfb 2012-03-21 06:23:14
您是否熟悉旅行商问题？这似乎是一个变种;一般来说，这是一种动态编程问题。 – Marcin 2012-03-20 12:19:32
我想补充说，链接的解决方案显然不是写得很容易和快速理解。尝试通过它。 – Marcin 2012-03-20 12:20:56
这个问题看起来像[聚类分析]（http://en.wikipedia.org/wiki/Cluster_analysis）和[Voronoi图表]（http://en.wikipedia.org/wiki/Voronoi_diagram）。我的想法是修改[k-均值聚类]（http://en.wikipedia.org/wiki/K-means_clustering）或其他[动态编程]（http://en.wikipedia.org/wiki/ Dynamic_programming）技术。 – 2012-03-20 12:08:27