Задача C. Троллейбусы ≡

Условие

Гоша и Андрюша очень любят ездить в троллейбусах. Обычно Гоша садится в некоторый троллейбус, а Андрюша садится в следующий троллейбус, следующий по тому же маршруту, и они едут, постоянно пытаясь увидеть в окно друг друга. Чем ближе их троллейбусы оказываются друг к другу, тем больше ребята радуются.

Скоро в городе появится новый кольцевой маршрут троллейбуса. Гоша достал откуда-то схему маршрута и теперь просит вас сказать ему, насколько близко к Гошиному троллейбусу будет проезжать следующий троллейбус того же маршрута.

Новый маршрут имеет форму n-звенной замкнутой ломаной, возможно, с самопересечениями и самокасаниями. Троллейбусы ездят по нему с постоянной скоростью. Для простоты будем считать, что они вообще не останавливаются. Также для простоты будем считать троллейбусы точками.

По маршруту будут циркулировать m троллейбусов, в каждой точке маршрута они будут появляться через равные промежутки времени. Гоша будет ехать на одном из троллейбусов, а Андрюша — на следующем.

Например, если четыре троллейбуса будут ездить по квадратному маршруту, то в каждый момент времени они будут находиться в соответствующих точках на разных сторонах квадрата (кроме тех моментов, когда все четыре окажутся в вершинах).

В этом случае минимальное расстояние между соседними троллейбусами будет достигаться в момент, когда троллейбусы окажутся в серединах сторон квадрата.

Формат входного файла

Первая строка входного файла содержит два целых числа n и m — количество прямых отрезков в маршруте и количество троллейбусов на нем.

Каждая из следующих n строк входного файла содержит два целых числа — координаты соответствующей вершины n-звенной ломаной. Координаты вершин приведены в порядке, в котором их будут проезжать троллейбусы.

Формат выходного файла

Ограничения

Примеры тестов

4 4
0 0
0 1
1 1
1 0

0.707106781186547524