给你 $$$n$$$ 个圆圈和两个整数参数 $$$k$$$ 和 $$$\ell$$$。第 $$$i$$$ 个圆的半径为 $$$r_i$$$,并且 $$$r_i \ge r_j$$$ 对于每个 $$$1 \le i \lt j \le n$$$ 成立。任务是在 2D 平面上绘制这些 $$$n$$$ 圆,以便同时满足以下条件。在讨论条件之前,让我们回顾一下:
- 每个圆都由其圆心 $$$O$$$ 和半径 $$$r$$$ 唯一确定。
- 半径为 $$$r$$$ 的圆定义为距圆心 $$$O$$$ 距离为的所有点的集合 正是 $$$r$$$。此任务中考虑的所有距离都是欧几里德距离。
- 圆的内部区域定义为距圆心$$$O$$$ 的距离为的所有点的集合 小于 $$$r$$$。
- 我们说一圈$$$C$$$ 附上 如果$$$C^\prime$$$的所有点都位于$$$C$$$的内部区域内,则另一个圆$$$C^\prime$$$。
您需要绘制这些 $$$n$$$ 圆圈以满足以下所有条件:
- 所有圆的中心共线。
- 任意两个中心之间的距离最多为$$$k$$$。
- 没有两个圆相交。
- 如果一个圆包含两个圆 $$$C$$$ 和 $$$C^\prime$$$,则 $$$C$$$ 包含 $$$C^\prime$$$ 或 $$$C^\prime$$$ 包含 $$$C$$$。
- 第一个 $$$\ell$$$ 圆圈 可能会也可能不会 被其他圆圈包围,而剩余的每个 $$$n - \ell$$$ 圆圈 必须 至少被一个圆圈包围。
满足上述所有条件的排列称为 可行。对于可行的排列 $$$\mathcal{A}$$$,定义其 质量 $$$d(\mathcal{A})$$$ 作为属于不同圆的任意两点之间的最小距离。
如果给定情况存在至少一种可行的安排,则输出所有可行安排中的最大可能质量。如果不存在可行的安排,则输出$$$0$$$。
样本输入 1 的可行安排。
一种安排是 不可行 用于示例输入 1。 输入
第一行包含三个整数$$$k$$$、$$$n$$$和$$$\ell$$$,分别代表圆心之间的最大距离、要绘制的圆的数量以及可能或可能不被其他圆包围的圆的数量。
第二行包含 $$$n$$$ 整数 $$$r_1, r_2, \ldots, r_n$$$,其中 $$$r_i$$$ 是第 $$$i$$$ 个圆的半径。
- $$$1 \le k \le 10^9$$$
- $$$2 \le n \le 10^5$$$
- $$$1 \le \ell \le \min\{n, 200\}$$$
- $$$1 \le r_i \le 10^9$$$
- $$$r_i \ge r_j$$$ 对于每个 $$$1 \le i \lt j \le n$$$。
输出
如果不存在可行的安排,则输出单个整数$$$0$$$。
否则,按以下格式输出所有可行排列 $$$\mathcal{A}$$$ 中最大可能的质量 $$$d(\mathcal{A})$$$:
- 如果 $$$d(\mathcal{A})$$$ 是整数,则将其输出为单个整数。
- 如果 $$$d(\mathcal{A})$$$ 不是整数,则以有理形式 $$$a/b$$$ 输出,使得 $$$1 \le a, b \le 10^9$$$, $$$\gcd(a,b) = 1$$$,并且 $$$|d(\mathcal{A}) - a/b|$$$ 被最小化。如果多个此类表格满足约束条件,则打印任何一个。
示例
输入复制
15 4 3 7 5 3 1
输出复制
3
输入复制
14 6 1 7 5 4 3 2 1
输出复制
1
输入复制
14 2 2 5 4
输出复制
5
输入复制
22 4 4 4 4 1 1
输出复制
10/3
输入复制
13 3 3 6 3 1
输出复制
4
注意
示例1说明: 第一张图展示了一种可行的布置,其中每个圆圈及其中心都以独特的颜色显示。
在这种布置中,属于不同圆的任意两点之间的最小距离是$$$3$$$,并且见证该距离的两个点被标记为红点。因此,这种安排的质量是$$$3$$$,这是这种情况下所有可行安排中可能的最大质量。请注意,只有圆 $$$4$$$ 需要包含在另一个圆中,而其余圆可以包含也可以不包含。
第二张图显示了一种安排 不可行。在这种情况下,圆 $$$1$$$ 包围圆 $$$3$$$ 和圆 $$$4$$$,但这两个圆都不包围另一个圆,从而违反了条件 $$$4$$$。