会合点 - Problem

欢迎来到 2022 ICPC（国际大学生程序设计竞赛）桃园区域赛！ICPC 是一项面向大学生的算法程序设计竞赛，旨在展示大学生的创造力、团队协作能力以及在压力下编写代码、分析和解决问题的能力。

今年，桃园区域赛共有 $N$ 位命题人（编号从 $1$ 到 $N$）。为了提高整个竞赛的质量，命题人在准备期间举行了多次会议。

如何选择会议地点是一个非常重要的问题，因为必须考虑命题人的住所。

为了方便起见，组织者将命题人分成了 $K$ 个小组。每个小组由编号连续的命题人组成，且每位命题人只属于一个小组。

对于同一个命题人小组，他们将使用同一个会议地点，该小组的代价定义为小组成员到会议地点的最远距离。

现在，已知 $N$ 位命题人的位置（二维笛卡尔坐标系上的点）以及 $K$，你能求出这 $K$ 个小组代价之和的最小值吗？

此处的距离指欧几里得距离，即对于两个点 $(x_1, y_1)$ 和 $(x_2, y_2)$，它们之间的距离为 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$。

这个问题对你来说可能有点难，此外，你意外发现了一条信息，但不知道它是否有用。也就是说，每位命题人的住所满足特定的公式。换句话说，$N$ 个点由以下公式生成：

$X_i = Y_{i-1} \times 233811181 + 1 \pmod{2^{31} - 1}, \forall i \ge 2$ $Y_i = X_i \times 233811181 + 1 \pmod{2^{31} - 1}, \forall i \ge 1$

以上故事纯属虚构，如有雷同，纯属巧合。

第一行包含三个整数 $N, K, X_1$，分别代表点的数量、区间的数量以及随机种子。

输出一个浮点数，表示 $K$ 个段中最小包围圆半径之和的最小值。

如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。形式化地，设你的答案为 $a$，标准答案为 $b$，若满足 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$，则你的答案被视为正确。

100 23 213

1319350480.8007326126

QOJ.ac