algorithm - 二分查找相关的编程难题

Question

我正在尝试解决以下问题，这是编程竞赛的一部分:

---

问题编号:CIELLAND

大厨 Ciel 开发了一座新岛屿和她的餐厅。夏尔打算在岛上 build N家餐厅，第i家餐厅的坐标为(xi,yi)。另外，夏尔要开辟K条道路，具体位置尚未确定。每条路都必须是一条无限长的直线。

令 di 为第 i 家餐厅与距离第 i 家餐厅最近的道路之间的距离。 Ciel 想要创建 K 条道路，使 max(d1, d2, ..., dN) 最小化。您的任务是计算 max(d1, d2, ..., dN) 的最小值。

---

关于我应该如何处理它有什么想法吗？此外，竞赛社论已经发布(http://www.codechef.com/wiki/march-2012-cook-problem-editorials)，但我无法理解解决方案。

任何有关要遵循的方法的帮助将不胜感激。

Answer 1

在高层次上，他们正在重新表述问题，以便更容易解决。通过转换下方的光线，他们限制了可能考虑的线路数量。

Problem A: There are N circles. The center of the i-th circle is (xi, yi) and all circles have the radii R. And let we can draw X lines such that any circle intersects with at least one line. What is the minimal X?

为了进一步解释，让我们用文字重新表述问题 A:餐厅严格遵守规则，并且有一条规则规定所有餐厅必须就距道路的单一最大距离达成一致 - 这将是 R。创建的圆圈由餐厅和 R 表示线需要相交的地方以满足此要求。新问题要求最少的道路数。

如果这在 Under K roads 中是不可能的，那么就必须做出一些改变。我们不能根据原始问题添加道路，但我们可以修改 R。这就是二分查找的用武之地，但我们必须先解决问题 A。

Now, let's consider solving Problem A. At first, the lines can be limited to common tangents to two circles. Because if a line intersects with some (at least 2) circles, we can move the line such that a moved line intersects with the same circles, and the moved line is one of common tangents. If a line intersects less than 2 circles, it is useless (but be careful of the case N = 1). There are at most 4 lines that is common tangents to two circles, so we consider at most 2 * N * (N-1) lines.

重要的部分是这个，我们需要找到与多个圆相交的线。最多需要考虑每对圆圈中的四行，查看源代码实现。

下一个重要步骤是动态规划，找到覆盖所有圆圈的最少行数。 “掩码”是一个位掩码，指示在考虑每条线时哪些圆圈已被击中。

这解决了问题，但现在我们必须转换回来。还记得 R 吗？我们现在可以通过二分查找来找到满足 X<=K 的最小 R。就我对问题 A 的重新表述而言，它是所有餐厅都同意且仍由道路提供服务的最小距离

希望对您有所帮助，这个棘手但有趣的问题。