Tokitsukaze and Explosion
Contest: Codeforces Round 573 (Div. 1)
Difficulty rating: 3100
Tags: binary search, greedy

Tokitsukaze and her friends are trying to infiltrate a secret base built by Claris. However, Claris has been aware of that and set a bomb which is going to explode in a minute. Although they try to escape, they have no place to go after they find that the door has been locked.

At this very moment, CJB, Father of Tokitsukaze comes. With his magical power given by Ereshkigal, the goddess of the underworld, CJB is able to set $$$m$$$ barriers to protect them from the explosion. Formally, let's build a Cartesian coordinate system on the plane and assume the bomb is at $$$O(0, 0)$$$. There are $$$n$$$ persons in Tokitsukaze's crew, the $$$i$$$-th one of whom is at $$$P_i(X_i, Y_i)$$$. Every barrier can be considered as a line with infinity length and they can intersect each other. For every person from Tokitsukaze's crew, there must be at least one barrier separating the bomb and him, which means the line between the bomb and him intersects with at least one barrier. In this definition, if there exists a person standing at the position of the bomb, any line through $$$O(0, 0)$$$ will satisfy the requirement.

Although CJB is very powerful, he still wants his barriers to be as far from the bomb as possible, in order to conserve his energy. Please help him calculate the maximum distance between the bomb and the closest barrier while all of Tokitsukaze's crew are safe.

Input format:
The first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$), indicating the number of people and the number of barriers respectively.

The $$$i$$$-th line of the next $$$n$$$ lines contains two integers $$$X_i$$$, $$$Y_i$$$ ($$$-10^5 \leq X_i, Y_i \leq 10^5$$$), indicating the $$$i$$$-th person's location $$$P_i(X_i, Y_i)$$$. Note that $$$P_i$$$ may have the same coordinates as $$$P_j$$$ ($$$j \neq i$$$) or even $$$O$$$.

Output format:
Print a single real number — the maximum distance meeting the requirement. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
In the first two examples, CJB must set the barrier crossing $$$O(0, 0)$$$.

In the last two examples, CJB can set each barrier crossing some $$$P_i$$$ such that the barrier is perpendicular to the line between $$$P_i$$$ and $$$O$$$.

Example input:
3 1
2 0
0 2
-1 0

Example output:
0.0000000000

Example input:
1 1
0 0

Example output:
0.0000000000

Editorial:
It is obvious that we can binary search the answer because we can pull any line closer to $$$O$$$ and the situation won't change. Applying a binary search, we focus on if it is possible to set $$$m$$$ barriers with the same distance to $$$O$$$ and meet the requirement. By doing so, we can draw a circle whose center is $$$O$$$ such that the closest point to $$$O$$$ on each barrier is on the circumference. Then it becomes a classic problem — for each barrier we can get the angle range of its closest point on the circle, and we have to choose at most $$$m$$$ points on the circle to ensure that there is at least one point within each range.
This kind of greedy trick is very simple on a sequence. As to ranges on a sequence, you only have to sort all ranges in increasing order of left endpoint and take every necessary right endpoint. As to ranges on a circle, you can enumerate a position to break the circle into a sequence. But if you enumerate as the same way on the sequence, the time complexity will be $$$\mathcal{O}(n^2)$$$ which is not enough.
Instead, we can double and extend these ranges into $$$2 n$$$ ranges and then regard them as on a sequence. We can do some precalculation, such as if we want to choose a point to cover the $$$i$$$-th sorted range and other ranges in its right as many as possible, what is the next range that we cannot cover. Let's denote that as $$$f[i][0]$$$, and then we can calculate the next range after $$$2^p$$$ repeated steps from the $$$i$$$-th range as $$$f[i][p]$$$, which can be obtained from $$$f[f[i][p - 1]][p - 1]$$$. After preparation, we can enumerate the beginning position and use binary lifting method, each time in complexity $$$\mathcal{O}(\log m)$$$, to know that whether we can use $$$m$$$ steps to cover all the ranges.
Therefore, the total time complexity can be $$$\mathcal{O}(n \log m \log D)$$$, where $$$D$$$ is the precision requirement.