城市$$N$$开通了一条新的公交路线。该路线是该地点的一条闭合多边形线,所有线段均平行于其中一个轴。 m 巴士将在该路线上运行。所有公交车都以相同的恒定速度沿着路线沿同一方向循环移动(在此问题中,停车时间可以忽略不计)。
公交车在路线的第一个顶点以等间隔开始运行。假设 T 是单辆公交车行驶整个路线的总时间。那么,公交车1在时间0开始移动,公交车2在时间T/m开始,公交车3在时间2T/m开始,以此类推;最后,公交车 m 在时间 (m - 1)T / m 开始移动。因此,连续总线对之间的所有间隔(包括最后和第一辆总线之间的间隔)都是相等的。
公交车可以通过同等功率的无线发射器相互通信。如果发射器的功率为 D,则只有彼此距离为 D 内的总线才能进行通信。
公交车还配备了分布式时刻表跟踪系统。为了让所有公交车都遵守时间表,系统必须不时同步所有公交车之间的必要数据。在同步时刻,总线 1 与总线 2 通信,总线 2 — 与总线 3 通信,依此类推;此外,总线 m 与总线 1 通信。
作为一名研究员工,您的任务是找到 D 的最小值,以便可以在所有公交车开始移动后找到执行同步的时刻。
输入
第一行包含两个整数 n 和 m (2 ≤ n, m ≤ 105) - 分别是折线的顶点数和总线数。
接下来的 n 行按遍历顺序描述路线的顶点。每行包含两个整数 xi, yi (- 1000 ≤ xi, yi ≤ 1000) - 各自顶点的坐标。
确保路线的每条路段(包括最后一个顶点和第一个顶点之间的路段)平行于其中一个坐标轴。此外,该路线没有两个后续顶点重合。路线允许有自交点,并且可以多次沿同一路段行驶。
输出
打印一个实数——问题的答案。如果相对误差或绝对误差不超过 10 - 6,您的答案将被接受。
示例
输入 #1
4 2 0 0 0 1 1 1 1 0
输出 #1
1.000000000
输入 #2
2 2 0 0 1 0
输出 #2
0.000000000
注意
假设每辆公交车每秒行驶 1 个距离单位。
在第一个示例中,0.5 秒内公交车将到达距离 1,因此我们可以选择 D = 1。
在第二个示例中,0.5 秒内两条总线都将处于 (0.5, 0),因此我们可以选择 D = 0。