Повадился как-то Братец Кролик в сад к Братцу Медведю лазить за финиками. Лазит и лазит, прямо спасу нет.
Обнёс Братец Медведь сад столбами, n штук всего вкопал. Обошёл вокруг сада несколько раз с колючей
проволокой — забор получился. Теперь-то, думает, можно за финики не беспокоиться. Ан нет, глядит,
на следующий день весь сад в следах Братца Кролика и косточками от фиников усеян. Что делать? Тут Братец Волк
ему и посоветовал: «Ты натяни через сад верёвки с колокольчиками. Пойдёт Братец Кролик за финиками,
заденет верёвку — ты это сразу услышишь.»
Послушался Братец Медведь, и пошли они натягивать верёвки между заборными столбами. Встанет Братец Волк
у одного столба, привяжет к нему один конец верёвки, а Братец Медведь отсчитает по кругу против часовой стрелки
k − 1 столб и к k-му другой конец верёвки привяжет. После этого Братец Волк перейдёт
к другому столбу, и так далее, пока они от всех столбов верёвки не натянули. Разошлись по домам довольные.
Спал в эту ночь Братец Медведь чутко, однако ничего не слышал. Утром выходит в сад — и что же видит?
Не такой дурак оказался Братец Кролик, он колокольчики заметил и через верёвки не прыгал. Он финики собирал
только там, куда мог подойти, не перепрыгивая верёвок. Огорчился было Братец Медведь, а потом
обрадовался — половину-то сада он сберёг. Или не половину, а меньше? Никак не может Братец Медведь
подсчитать, помогите же ему в этом.
Исходные данные
В первой строке находятся числа n и k (3 ≤ n ≤ 300;
1 ≤ k < n). Далее в n строках перечислены координаты всех столбов забора
в порядке обхода против часовой стрелки. Все координаты целые и по модулю не превосходят 10000.
Сад можно считать строго выпуклым, то есть любой отрезок, соединяющий две точки, принадлежащие разным сторонам
забора, полностью лежит внутри сада и может касаться забора только в самих этих точках.
Результат
Выведите с точностью до 10−4 отношение спасённой верёвками площади сада ко всей площади внутри
забора.
Примеры
исходные данные | результат |
---|
5 3
0 0
20 0
20 20
10 30
0 20
| 0.466666667
|
6 2
0 2
-2 1
-2 -1
0 -2
2 -1
2 1
| 0.666666667
|
Автор задачи: Павел Егоров
Источник задачи: Открытое личное первенство УрГУ 2009 (28 февраля 2009)