ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Открытое личное первенство УрГУ 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Сад-огород

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Повадился как-то Братец Кролик в сад к Братцу Медведю лазить за финиками. Лазит и лазит, прямо спасу нет. Обнёс Братец Медведь сад столбами, 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)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1681. Сад-огород