题目背景

$\text{加强版}\Leftarrow$

题目描述

$N$ 个点，第 $i$ 个点坐标为 $(x_i,y_i)$。

定义一束激光：$y=kx$，若点 $i$ 满足到该条直线距离 $\le d$，认为被激光击中。

求使用至多 $K$ 束激光，击毁图中所有点的最小代价 $d$。

输入格式

第一行输入两个正整数 $N,K$。

第 $2 \sim N+1$ 行，每行两个非负整数 $x_i,y_i$，表示第 $i$ 个点的坐标。

输出格式

第一行输出最小代价 $d$，保留到小数点后 $2$ 位。

2 1
2 3
6 3

1.20

4 3
1 6
4 6
4 2
4 0

0.97

提示

样例说明

样例 $\#1$ 中两蓝色点坐标分别为 $(2,3)$ 和 $(6,3)$，到直线 $y=\frac{3}{4}x$ 的距离均为 $\frac{6}{5}=1.2$，因此输出 1.20。	样例 $\#2$ 中坐标为 $(4,0),(4,2)$ 的点与斜率为 $\frac{1}{4}$ 的直线之间距离为 $\frac{4}{17}\sqrt{17}\approx0.97014\dots$，因此输出 0.97。

可以证明两个样例中的方案是最优的，因此所求的 $d$ 是最小的。

提示

1. 可能会用到的公式：点 $(x_0,y_0)$ 到直线 $y=kx$ 的距离是 $\dfrac{|y_0-kx_0|}{\sqrt{k^2+1}}$。
2. 对于 C++ 选手，建议使用 变量类型 long double 进行数值计算。
   输出时请用形如 printf("%.2Lf",ans) 的形式输出答案，注意 %.2Lf 中的 L 是大写。
3. 本题中存在的浮点数运算可能较多，虽然已经增大时限，但仍然请注意常数因子对程序效率的影响。

数据范围

本题采用捆绑测试。

记 $M$ 为所有 $x_i,y_i$ 的最大值。

Subtask	Score	$M\le$	$K\le$
$1$	$30$	$10$	$1$
$2$		$1.5\times10^4$
$3$	$40$

对于 $100\%$ 的数据：$1\le N,M,K\le2.5\times10^4$。

所有数据均保证不存在相同的 $(x_i,y_i)$ 出现多次。

---

后记

冰魄战龙我吹爆 $\sim$

如果您也热爱 ddt，请在比赛结束后找到出题人，并把他虐一顿。

出题人推荐阅读题解：（优点：显然）https://www.luogu.com.cn/blog/_post/362493