algorithm - 用一条线将一组圆分成 2 个相等的两半

Question

几个月来我一直在尝试回答这个问题，但我仍然卡住了。

题目要求我写一个程序，输出YES或NO给定的集合是否有一条线可以分割它。

我正在寻找一种可能的算法来确定答案，一旦我牢牢掌握了答案，我想将其解释为代码。

在 2D 平面上给定一组均匀长度的圆，保证不接触。确定是否可以通过集合画一条线，将其精确地一分为二而不与任何圆相交。

• 圆半径大于零
• 没有一个圆圈相互接触或包含在一起
• 长度为2的集合总是可能的
• 每个圆的大小都可以是唯一的

输入格式:

N - number of circles in set
x y r - N lines of: x coordinate, y coordinate, radius
Input repeats until EOF

为每个测试用例输出 YES 或 NO

示例输入:

4
0 0 20
0 40 20
0 30 10
40 -30 10
4
0 0 20
0 40 20
20 40 20
20 -40 20

输出:

YES
NO

---

编辑:我尝试解决

第一次尝试 是在每个圆都是零半径点的情况下找到可以解决此问题的所有直线，以便为我提供一组可能的问题解决方案。

链接到 Dividing a plane of points into two equal halves

之后我会返回半径，然后遍历每个可能的解决方案。

这个算法非常慢(我没有费心计算 O 时间，因为所需的算法需要在合理的秒时间范围内运行)

---

我的第二次尝试是将这些圆投影到 y 轴和 x 轴上并旋转集合，直到在分割设置为两个。

此方法只需要最大旋转 1/2pi 弧度即可确定答案，但编程尝试既复杂又缓慢。

---

我在网上找不到任何地方的问题，因为它是我大学的一位教授去年在纸上提出的。

Answer 1

具有三次复杂度的简单算法:

找出所有圆对的公切线。有 4*n*(n-1)/2 ~ n^2 条切线。

对于每条切线，检查它是否与所有圆相交。 n*n^2=n^3 操作

---

我认为可能存在复杂度更高的算法(基于切线方向排序)