Background

$\text{Enhanced Version}\Leftarrow$

Problem Description

There are $N$ points. The coordinates of point $i$ are $(x_i,y_i)$.

Define a laser beam as the line $y=kx$. If point $i$ has distance $\le d$ to this line, it is considered hit by the laser.

Find the minimum cost $d$ such that using at most $K$ laser beams can destroy all points in the figure.

Input Format

The first line contains two positive integers $N,K$.

Lines $2 \sim N+1$ each contain two non-negative integers $x_i,y_i$, representing the coordinates of point $i$.

Output Format

Output the minimum cost $d$ on the first line, rounded to $2$ digits after the decimal point.

2 1
2 3
6 3

1.20

4 3
1 6
4 6
4 2
4 0

0.97

Hint

Sample Explanation

In Sample $\#1$, the two blue points have coordinates $(2,3)$ and $(6,3)$. Their distances to the line $y=\frac{3}{4}x$ are both $\frac{6}{5}=1.2$, so the output is 1.20.	In Sample $\#2$, the points with coordinates $(4,0),(4,2)$ have distance $\frac{4}{17}\sqrt{17}\approx0.97014\dots$ to the line with slope $\frac{1}{4}$, so the output is 0.97.

It can be proven that the solutions in both samples are optimal, so the required $d$ is minimal.

Notes

1. A formula you may need: the distance from point $(x_0,y_0)$ to the line $y=kx$ is $\dfrac{|y_0-kx_0|}{\sqrt{k^2+1}}$.
2. For C++ users, it is recommended to use the variable type long double for numerical computation.
   When outputting, please use a form like printf("%.2Lf",ans). Note that the L in %.2Lf is uppercase.
3. This problem may involve many floating-point operations. Although the time limit has been increased, please still pay attention to constant factors that affect performance.

Constraints

This problem uses bundled testdata.

Let $M$ be the maximum value among all $x_i,y_i$.

For $100\%$ of the data: $1\le N,M,K\le2.5\times10^4$.

All testdata guarantee that no identical $(x_i,y_i)$ appears more than once.

Afterword

I totally love Ice Soul War Dragon $\sim$

If you also love ddt, please find the problem setter after the contest ends and beat him up.

The setter recommends reading the solution editorial (advantage: obvious): https://www.luogu.com.cn/blog/_post/362493

Translated by ChatGPT 5