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

Открытый чемпионат УрГУ 2009

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

B. Забытые технологии

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Зима. Конец декабря. Падает снег. Ветер подхватывает снежинки и со свистом проносит их меж каменных строений. Монастырь выглядит заброшенным — двери занесены снегом, окна плотно прикрыты ставнями. Лишь только окна скриптория — самые большие в монастыре — распахнуты настежь. Неяркий зимний свет падает в просторную комнату, где в полной тишине сидят несколько монахов. В комнате настолько холодно, что пальцы монахов немеют. Но они продолжают торопливо писать гусиными перьями, стараясь успеть как можно больше за короткий декабрьский день.
В скриптории совершается великое таинство — идёт копирование информации.
Один монах, бывший подмастерье, пишет свою первую книгу. Его губы шевелятся, он неслышно повторяет каждую строчку, чтобы не допустить ошибки. Другой переписал уже десятки книг. Каждая выведенная им буква неотличима от оригинала. Он занимается этим всю свою жизнь и не умеет ничего другого.
В соседнем помещении сидит монах, которого называют корректор. Он занимается не менее важным делом — расставляет на полях книги пометки и исправления. Также в скриптории работают иллюминаторы и переплётчики, придающие книге тот вид, в котором она попадает в руки богатых мирян. Труд всех этих людей является одним из столпов экономики монастыря.
Но свет тускнеет, монахи откладывают свои перья и расходятся по кельям. Заканчивается день. Заканчивается 1439 год. Заканчивается эпоха монахов-переписчиков. В следующем, 1440 году, Иоганн Гутенберг напечатает свою первую книгу.
***
Осень. Середина ноября. Идёт дождь. Молодая девушка сидит в закусочной на пересечении 112-й улицы и Бродвея. Она смотрит в окно на свинцовые тучи, нависающие над городом. Возможно, всё дело в погоде, но с самого утра девушка чувствует странную пустоту в душе. Она чувствует себя безучастным наблюдателем, которому нет дела ни до чего вокруг.
К девушке подходит официант и наливает в её кружку кофе до половины. Она поднимает глаза, пытаясь протестовать, но официант уже не смотрит на неё. Он смотрит на женщину, которая входит в закусочную и отряхивает зонтик. На его лице появляется улыбка, и он рассыпается в любезностях. Девушка отворачивается от них и наливает молока в свой кофе.
Чтобы чем-то занять себя, она берёт свежую газету. В ней нет ничего интересного, кроме истории об актёре, который, будучи в состоянии алкогольного опьянения, упал у себя в квартире и умер. Впрочем, имя этого актёра ей ничего не говорит. Она перелистывает страницы в поисках гороскопа и карикатур.
Ей кажется, что на неё кто-то смотрит. Она поворачивает голову и видит женщину за окном, смотрящую внутрь. Через секунду она понимает, что женщина всего лишь смотрит на своё отражение, поправляя юбку и подтягивая чулки.
А дождь всё льёт и льёт. До девушки доносится звон колоколов собора Иоанна Богослова, расположенного неподалёку. Этот звон будит в ней старые воспоминания о её друге, о том, как они когда-то сидели вдвоём на ступенях этого собора в полпервого ночи.
Девушка допивает кофе и выходит из закусочной. На вывеске написано «У Тома». Девушку зовут Сюзанна Вега. Через несколько месяцев она напишет песню об этом утре. А ещё через десять лет специалист по кодированию звука из Германии использует эту песню для отладки своего нового метода сжатия. Он прослушает эту песню тысячи раз, прежде чем финальная версия алгоритма, который впоследствии назовут MP3, будет готова.
***
В Музее истории науки, в зале «Забытые технологии» есть экспонат, который называется «Жертвы массового копирования». Под стеклом на сукне лежит рукописная книга конца XV века, а на ней — компакт-диск конца XX века. Обе эти технологии были забыты после изобретения качественно новых способов копировать и распространять информацию. Рукописные книги не смогли конкурировать с дешёвой продукцией печатных прессов, так же как компакт-диски были вытеснены повсеместным распространением цифровых сетей. И теперь их можно найти только в частных коллекциях да в этом музее.
А ещё в этом музее живёт маленькая мышка. Она живёт там потому, что ей нравится всё необычное. Она прогрызла снизу дырку в сукне, и теперь ей хочется откусить хотя бы маленький кусочек от блестящего диска и утащить его себе в нору. Но она боится, что не успеет сделать это до того, как сработает сигнализация. Помогите ей найти кратчайший путь до диска.
Книга представляет собой прямоугольник. На книге лежит диск, его центр находится либо внутри прямоугольника, либо на его границе. Мышка может бегать только по сукну, её собственными размерами можно пренебречь. В начальном положении мышка находится на ненулевом расстоянии от книги и диска. Чтобы откусить кусочек от диска, мышка должна подбежать к той его точке, что находится строго за пределами прямоугольника, то есть свободно висит над сукном.

Исходные данные

В первой строке указаны координаты вершин прямоугольника, перечисленные в порядке обхода против часовой стрелки. В следующей строке указаны координаты центра диска и его радиус. В третьей строке указаны координаты начального положения мышки. Все числа целые и не превышают по модулю 1000. Радиус диска больше либо равен 1.

Результат

Выведите длину кратчайшего пути до диска с точностью не менее 10–5. Гарантируется, что искомый путь существует.

Пример

исходные данныерезультат
-4 -3 8 6 5 10 -7 1
1 7 5
7 -1
12.07107
Автор задачи: Павел Атнашев (идея — Алексей Самсонов)
Источник задачи: XIV Открытый командный чемпионат УрГУ по программированию
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1733. Забытые технологии