플롯

평면 위의 점들의 수열을 플롯(plot) 이라고 부른다. 주어진 플롯 $(P_1, \dots, P_n)$ 을, 원래 플롯과 가장 비슷하면서도 점의 개수가 최대 $m$ 개 ($m \le n$) 이하인 다른 플롯으로 바꾸려고 한다.

새 플롯은 다음과 같이 만든다. 수열 $(P_1, \dots, P_n)$ 을 $s$ 개 ($s \le m$) 의 연속한 부분수열로 나눈다.

$(P_{k_0+1}, \dots, P_{k_1}),\ (P_{k_1+1}, \dots, P_{k_2}),\ \dots,\ (P_{k_{s-1}+1}, \dots, P_{k_s})$

여기서 $0 = k_0 < k_1 < k_2 < \dots < k_s = n$ 이다. 그런 다음 각 부분수열 $(P_{k_{i-1}+1}, \dots, P_{k_i})$ ($i = 1, \dots, s$) 을 하나의 새로운 점 $Q_i$ 로 대체한다. 이때 점 $P_{k_{i-1}+1}, \dots, P_{k_i}$ 각각이 점 $Q_i$ 로 축약(contract) 되었다고 말한다. 그 결과 점 $Q_1, \dots, Q_s$ 로 이루어진 새 플롯이 만들어진다.

새로 만든 플롯이 원래 플롯과 얼마나 닮았는지는, 모든 점 $P_1, \dots, P_n$ 에서 자신이 축약된 점까지의 거리 중 최댓값으로 측정한다.

$\max_{i=1,\dots,s} \left( \max_{j=k_{i-1}+1,\dots,k_i} d(P_j, Q_i) \right)$

여기서 $d(P_j, Q_i)$ 는 두 점 사이의 거리이며, 다음 공식으로 주어진다.

$d((x_1, y_1), (x_2, y_2)) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$

위 그림은 예시 플롯 $(P_1, \dots, P_7)$ 과 새 플롯 $(Q_1, Q_2)$ 를 나타낸다. 여기서 $(P_1, \dots, P_4)$ 는 $Q_1$ 로, $(P_5, P_6, P_7)$ 은 $Q_2$ 로 축약되었다.

$n$ 개의 점으로 이루어진 플롯이 주어질 때, 점의 개수가 최대 $m$ 개 이하이면서 원래 플롯과의 닮음 척도(위에서 정의한 최대 축약 거리)가 최소가 되도록 플롯을 만들 수 있다. 연속한 부분수열로 나누는 방법은 자유롭게 정할 수 있다. 이때 가능한 최소 닮음 척도 $d$ 를 구하여라.

첫째 줄에 두 정수 $n$ 과 $m$ 이 공백 하나로 구분되어 주어진다 ($1 \le m \le n \le 100000$). 이어지는 $n$ 개의 줄 중 $i$ 번째 줄에는 두 정수 $x_i$ 와 $y_i$ 가 공백 하나로 구분되어 주어지며 ($-1000000 \le x_i, y_i \le 1000000$), 이는 점 $P_i$ 의 좌표 $(x_i, y_i)$ 를 나타낸다.

첫째 줄에 실수 하나 $d$ 를 출력한다. $d$ 는 점의 개수가 $m$ 개 이하가 되도록 만들 수 있는 모든 플롯에 대하여, 원래 플롯과의 닮음 척도(각 점에서 자신이 축약된 점까지 거리의 최댓값)의 최솟값이다. 소수점 아래 정확히 $6$ 자리까지 반올림하여 출력한다.