← 返回题目列表

AtCoder · oupc2023_day1_m

M. 不能UT

中文机器翻译题面 查看原题

配点 : 100 点

問題文

xy 飞机上的银杏叶 有 N 件。 N 所有银杏叶都是圆形的, 第 i 片银杏叶中心坐标为(A_i,B_i) 且所有半径都相等。

从现在开始,这些 N 给银杏叶上色。 添加颜色之前 KowerKoint 你很平静,但是添加颜色之后,你可以 (i,j) (1\leq i < j \leq N) 的存在会导致不安。 第

  • i 片银杏叶内侧(不包括周长)和 j 银杏叶内部(不包括圆周)公共部分不为空
  • i 银杏叶的颜色和 j 银杏叶的颜色不一样。

KowerKoint 你喜欢色彩缤纷的风景,所以1 多于一片银杏叶的颜色数为 C 我希望它不止于此。 使用这种着色方法,找到银杏叶的最大半径,使得 KowerKoint 在着色后仍保持平静。 我们可以证明,在限制条件下,总存在最大值。

制約

  • 2 \leq C \leq N \leq 50{,}000
  • -10{,}000 \leq A_i, B_i \leq 10{,}000
  • (A_i,B_i) 都不同
  • 输入全为整数。

小課題

  1. (1 点) N \leq 1{,}000
  2. (99 点)无附加约束

入力

输入是按以下格式从标准输入给出的。 请输出

N C
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答案 1 行输出。

与正确值的绝对或相对误差为 如果满足以下条件,则 10^{-6} 被认为是正确的:


入力例 1

6 3
1 7
-7 0
2 -10
12 -4
6 7
1 -6

出力例 1

5.315073

半径是 \frac{\sqrt{113}}{2}=5.31507291\dots 以下情况,如下图所示。 3 您可以添加不同的颜色。

该测试用例满足子任务 1 的约束。


入力例 2

10 2
3789 5753
-9503 -3197
2918 -1274
-762 5030
-1343 -6275
2936 5844
640 -978
9997 -3756
-633 910
-8076 -6940

出力例 2

3750.752

该测试用例满足子任务 1 的约束。