CF2172C.Circles Are Far from Each Other

You are given $n$ circles and two integer parameters $k$ and $\ell$. The $i$-th circle has radius $r_i$ and $r_i \ge r_j$ holds for every $1 \le i \lt j \le n$. The task is to draw these $n$ circles on a 2D plane so that the following conditions are simultaneously satisfied. Before proceeding to the conditions, let us recall that:

• Each circle is uniquely determined by its center $O$ and radius $r$.
• A circle of radius $r$ is defined as the set of all points whose distance from its center $O$ is exactly $r$. All distances considered in this task are Euclidean.
• The interior region of a circle is defined as the set of all points whose distance from its center $O$ is less than $r$.
• We say that one circle $C$ encloses another circle $C^\prime$ if all points of $C^\prime$ lie inside the interior region of $C$.

You need to draw these $n$ circles to satisfy all of the following conditions:

1. The centers of all circles are collinear.

2. The distance between any two centers is at most $k$.

3. No two circles intersect.

4. If a circle encloses two circles $C$ and $C^\prime$, then either $C$ encloses $C^\prime$ or $C^\prime$ encloses $C$.

5. The first $\ell$ circles may or may not be enclosed by other circles, whereas each of the remaining $n - \ell$ circles must be enclosed by at least one circle.

An arrangement that satisfies all the above conditions is called feasible. For a feasible arrangement $\mathcal{A}$, define its quality $d(\mathcal{A})$ as the minimum distance between any two points belonging to different circles.

If there exists at least one feasible arrangement for the given case, output the maximum possible quality among all feasible arrangements. If no feasible arrangements exist, output $0$.

A feasible arrangement for sample input 1.

An arrangement that is not feasible for sample input 1.

给你 $n$ 个圆，以及两个整数参数 $k$ 和 $\ell$。第 $i$ 个圆的半径为 $r_i$，且对任意 $1 \le i < j \le n$ 均满足 $r_i \ge r_j$。你的任务是在二维平面上绘制这 $n$ 个圆，使得以下所有条件同时成立。在列出这些条件之前，我们先回顾如下定义：

• 每个圆由其中心 $O$ 和半径 $r$ 唯一确定。
• 半径为 $r$ 的圆定义为所有到其中心 $O$ 的距离恰好等于 $r$ 的点构成的集合。本题中所有涉及的距离均为欧几里得距离。
• 圆的内部区域定义为所有到其中心 $O$ 的距离严格小于 $r$ 的点构成的集合。
• 若圆 $C$ 的内部区域包含圆 $C^\prime$ 的所有点，则称圆 $C$ 包围（encloses）圆 $C^\prime$。

你需要绘制这 $n$ 个圆，使其满足以下全部条件：

1. 所有圆的中心共线。
2. 任意两个中心之间的距离至多为 $k$。
3. 任意两个圆互不相交。
4. 若某圆包围了两个圆 $C$ 和 $C^\prime$，则要么 $C$ 包围 $C^\prime$，要么 $C^\prime$ 包围 $C$。
5. 前 $\ell$ 个圆可以被其他圆包围，也可以不被包围；而其余 $n - \ell$ 个圆中的每一个都必须至少被一个圆包围。

满足上述所有条件的构型称为可行构型（feasible arrangement）。对于一个可行构型 $\mathcal{A}$，定义其质量（quality）$d(\mathcal{A})$ 为：属于不同圆的任意两点之间的最小距离。

若给定输入存在至少一个可行构型，则输出所有可行构型中可能达到的最大质量；若不存在任何可行构型，则输出 $0$。

样例输入 1 的一个可行构型。

样例输入 1 的一个不可行构型。

The first line contains three integers $k$, $n$, and $\ell$, representing the maximum distance between centers, the number of circles to be drawn, and the number of circles that may or may not be enclosed by other circles, respectively.

The second line contains $n$ integers $r_1, r_2, \ldots, r_n$, where $r_i$ is the radius of the $i$-th circle.

• $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$ for every $1 \le i \lt j \le n$.

第一行包含三个整数 $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$
• 对于所有 $1 \le i \lt j \le n$，均有 $r_i \ge r_j$。

If no feasible arrangements exist, output a single integer $0$.

Otherwise, output the maximum possible quality $d(\mathcal{A})$ among all feasible arrangements $\mathcal{A}$ in the following format:

• If $d(\mathcal{A})$ is an integer, output it as a single integer.
• If $d(\mathcal{A})$ is not an integer, output it in the rational form $a/b$ such that $1 \le a, b \le 10^9$, $\gcd(a,b) = 1$, and $|d(\mathcal{A}) - a/b|$ is minimized. If multiple such forms satisfy the constraints, print any.

如果不存在可行的安排方案，则输出单个整数 $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|$ 最小。若存在多个满足条件的分数形式，输出任意一个即可。

Explanation of Example 1: A feasible arrangement is illustrated in the first figure, where each circle and its center are shown in a unique color.

In this arrangement, the minimum distance between any two points belonging to different circles is $3$, and the two points witnessing this distance are marked as red dots. Hence, the quality of this arrangement is $3$, which is the maximum possible among all feasible arrangements for this case. Note that only circle $4$ is required to be enclosed within another circle, while the remaining circles may or may not be enclosed.

The second figure shows an arrangement that is not feasible. In this case, circle $1$ encloses both circle $3$ and circle $4$, but neither of these two circles encloses the other, thereby violating condition $4$.

示例 1 的说明：第一个图中展示了一种可行的排列方式，其中每个圆及其圆心均以唯一颜色标出。

在此排列中，属于不同圆的任意两点之间的最小距离为 $3$，且实现该最小距离的两个点以红色圆点标出。因此，该排列的质量为 $3$，是本例所有可行排列中所能达到的最大值。注意：仅要求圆 $4$ 必须被另一个圆所包含，其余各圆则可包含也可不包含于其他圆内。

第二个图展示了一种不可行的排列方式。此时，圆 $1$ 同时包含了圆 $3$ 和圆 $4$，但这两个圆彼此之间互不包含，从而违反了条件 $4$。