I. 圆盘 详细题解

题目核心理解

平面上有 $n$ 个圆盘，圆心固定，圆盘之间只允许相切、不允许重叠。 你可以修改每个圆盘的半径，要求满足：

1. 原来相切的圆盘仍然保持相切；
2. 修改后任意两个圆盘仍然没有正面积的重叠；
3. 所有圆盘半径的总和严格变小；
4. 新半径必须是正实数。

问是否存在合法的修改方案。

核心思路

1. 关键性质

• 把每个圆盘看作一个点，相切的圆盘之间连一条边，形成相切图。
• 若圆盘 $i$ 与圆盘 $j$ 相切，则半径变化量必须满足：$$\delta_i + \delta_j = 0$$
• 在同一个连通分量内，一旦某个点的 $\delta$ 确定，整个分量的 $\delta$ 都被唯一确定，只能取 $+\delta$ 或 $-\delta$。

2. 二分图判定

• 如果连通分量不是二分图（存在奇环），则只能 $\delta=0$，无法改变半径和。
• 如果连通分量是二分图，可将节点分为黑白两色：
  • 白色点变化量为 $+\delta$
  • 黑色点变化量为 $-\delta$
• 该分量的总半径变化量为：$$\delta \times (white - black)$$

3. 判定条件

只要存在任意一个连通分量满足：

• 是二分图；
• 黑白节点数量不相等； 就可以通过选择合适的 $\delta$ 让总半径严格减小，答案为 YES。 否则答案为 NO。

算法流程

1. 枚举每对圆盘，判断是否相切，构建相切图。
2. 对每个未访问的连通分量进行二分图染色。
3. 染色同时统计白色节点数与黑色节点数。
4. 如果某个分量是二分图且黑白数量不等，输出 YES。
5. 所有分量都不满足条件，输出 NO。

公式与复杂度分析

相切判定条件：

相切约束：

总半径变化量：

复杂度

• 建图：$O(n^2)$
• 连通分量染色：$O(n)$
• 总时间复杂度：$O(n^2)$

可轻松处理 $n\le 1000$ 的数据范围，在 $2$ 秒时限内稳定通过。