#P18615. Meeting Places

Meeting Places

Meeting Places

有 NN 位出题人,编号依次为 1,2,…,N1,2,\ldots,N。第 ii 位出题人的住所是二维平面上的点 (Xi,Yi)(X_i,Y_i)。

组织者要将他们恰好分为 KK 个非空组。每组由编号连续的出题人组成,每位出题人恰好属于一组。

每组可以在平面上任意选择一个开会地点。该组的费用为组内出题人的住所到这个地点的欧几里得距离的最大值。两点 (x1,y1)(x_1,y_1) 与 (x2,y2)(x_2,y_2) 的距离为

(x1−x2)2+(y1−y2)2.\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.

请确定分组及每组的开会地点,使所有组的费用之和最小。等价地,每组费用是包含该组所有点的最小覆盖圆的半径。

这些住所不是逐个给出的,而是由输入的 X1X_1 按下面的公式生成。令 M=231−1M=2^{31}-1,所有模运算均取 [0,M−1][0,M-1] 中的余数:

$$X_i=(Y_{i-1}\times233811181+1)\bmod M\qquad(i\ge2),$$Yi=(Xi×233811181+1) mod M(i≥1).Y_i=(X_i\times233811181+1)\bmod M\qquad(i\ge1).

特别地,第一个点的横坐标就是输入的 X1X_1。

输入格式

一行三个整数 N,K,X1N,K,X_1,分别表示点数、组数和生成点所用的种子。

输出格式

输出一个浮点数,表示恰好划分成 KK 段时最小的半径之和。

设你的输出为 aa,标准答案为 bb。当且仅当

∣a−b∣max⁡(1,∣b∣)≤10−6\frac{|a-b|}{\max(1,|b|)}\le10^{-6}

时认为答案正确。无需输出分组或开会地点。

数据范围

  • 1≤K≤N≤20001\le K\le N\le2000。
  • 1≤X1≤88311\le X_1\le8831。

样例输入 1

100 23 213

样例输出 1

1319350480.8007326126