Tokitsukaze and Explosion

题意翻译

### 题目描述 给定平面上$N$个关键点，现在你可以放置$M$条直线，直线之间可以相交，需要满足所有关键点与原点之间的线段至少与你放置的一条直线相交（相交在端点也算相交）。如果有一个关键点就是原点，那么一定要满足有一条直线经过原点。 你需要求出在满足上述条件的情况下原点到所有放置的直线的距离的最小值的最大可能值是多少。 ### 输入格式 第一行一个正整数$N(1 \leq N \leq 10^5)$表示关键点数量 接下来$N$行每行两个整数$X_i,Y_i (-10^5 \leq X_i,Y_i \leq 10^5)$描述一个关键点。 ### 输出格式 一行一个小数表示答案，当你与答案的相对误差或者绝对误差不超过$10^{-6}$时判为正确。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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} $ .

输入输出样例

输入样例 #1

3 1
2 0
0 2
-1 0

输出样例 #1

0.0000000000

输入样例 #2

1 1
0 0

输出样例 #2

0.0000000000

输入样例 #3

2 1
-1 -1
-1 -1

输出样例 #3

1.4142135617

输入样例 #4

3 100000
3 2
-1 -3
2 -5

输出样例 #4

3.1622776602

说明

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 $ .