Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
62. Стена
Выпуклая оболочкаОлимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 9F) |
| 24/07/2006 | Лето 2006 - 9 (нет результатов) (F) |
| 03/10/2007 | Занятие 4 (F) |
| 14/03/2009 | Занятие 15 (E) |
| 01/11/2012 | Занятие 8 (F) |
| 24/03/2015 | Занятие 18 (B) |
| 02/07/2016 | Лето 2016 - 4 (F) |
| 07/10/2023 | Тренировка 1 (проводит gribanov) (R) |
| 30/11/2023 | Геометрия 2 (проводит BOGAT) (H) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Жил-был жадный Король. Он приказал своему главному Архитектору построить стену вокруг его замка. Король был таким жадным, что не послушал предложение Архитектора построить красивую кирпичную стену совершенной формы с изящными высокими башнями. Вместо этого он приказал построить стену вокруг всего замка, используя минимальное количество камня, но потребовал, чтобы стена не подходила к замку ближе некоторого расстояния. Если Король узнает, что Архитектор использовал больше ресурсов для постройки стены, чем было абсолютно необходимо для удовлетворения требований, Архитектор лишится головы. Более того, Архитектор должен представить проект стены, где указано точное количество ресурсов.
Ваша задача – помочь бедному Архитектору сохранить голову, написав программу, определяющую минимальную длину стены, которую можно построить вокруг замка, удовлетворив требования Короля.
Задача слегка упрощается тем, что замок Короля представляет собой многоугольник и расположен на плоской поверхности. Архитектор уже сопоставил замку прямоугольную декартову систему координат и точно определил координаты каждого угла замка в футах.
Ввод
Первая строка содержит два целых числа `N` и `L`, разделённых пробелом: `N` – число углов в замке Короля, а `L` – минимальное число футов, на которое Король разрешил приблизить стену к замку.
Следующие `N` строк описывают координаты углов замка в порядке обхода по часовой стрелке. Каждая строка содержит два целых числа `x_i` и `y_i`, разделённых пробелом и представляющих собой координаты `i`-го угла в футах. Все углы имеют различные координаты, и стены замка не пересекаются иначе как в углах.
Ограничения: `3\ ≤\ N\ ≤\ 1000`, `1\ ≤\ L\ ≤\ 1000`, `-10\ 000\ ≤\ x_i,\ y_i\ ≤\ 10\ 000`.
Вывод
Выводится единственное число – минимальная длина стены в футах, которая может быть построена вокруг замка согласно требованиям Короля. Вы должны представить Королю целое число футов, потому что вещественные числа ещё не изобретены. Однако результат нужно округлить так, чтобы он отличался не более чем на 8 дюймов от правильного (1 фут = 12 дюймов), потому что большей неточности Король не потерпит.
Пример ввода
9 100 200 400 300 400 300 300 400 300 400 400 500 400 500 200 350 200 200 200
Пример вывода
1628
