P7806 Ice Soul Breath

[$\text{Enhanced Version}\Leftarrow$](/problem/U174529)

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.

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 the minimum cost $d$ on the first line, rounded to $2$ digits after the decimal point.

#### 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$. | Subtask | Score | $M\le$ | $K\le$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $30$ | $10$ | $1$ | | $2$ | $30$ | $1.5\times10^4$ | $1$ | | $3$ | $40$ | | | 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