Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Robbery
 

Задача  Robbery

 Будівля банку являє собою опуклий  багатокутник, координати вершин якого відомі, але зовсім не обов'язково задані в порядку обходу.  Банківські активи зберігаються в підвальному поверсі, що являє собою одну кімнату. Підвал знаходиться під усім приміщенням банку. Грабіжники дізналися, що в тому  районі міста, де знаходится банк, проходить  кільцевий горизонтальний каналізаційний колекттор ( для нефахівців в справах каналізаціїї - підземний коридор у вигляді кола) і проходить він трошки  глибше підвального приміщення банку. Допоможіть грабіжникам, що потрапили в колектор, розрахувати мінімальну довжину горизонтального тунеля, який їм треба прорити,   щоб  пограбувати банк.  Майте на увазі: як грабіжники потрапили в колектор - знають лише вони, а ось вийти з під землі вони можуть лише за межами банку. Автори задачі гарантують, що навіть  в випадку правильної відповіді Вам не буде висуното звинувачення в сприянні скоєнню злочину.

Технічні умови. Ви вводите з клавіатури   число вершин N, потім N пар (Xi Yi)   дійсних чисел -- координати вершин, а після координат останньої вершини - теж  дійсні кординати  (Xr Yr)  цетнру колектора та його радіус  R. Всі числа вводяться через пропуск. Ви виводите на екран одне дійсне число- довжину тунеля.. Вершин у багатокутника не більше 50, всі координати по модулю не перевищують 1000, а радіус колектора не більший 500.

Приклад
Введення:   4 1 1 3 2 1 2 3 0 -3 -3 2
Виведення:  3.65685424949334E+0000


Задача  Robbery

Здание банка представляет собой выпуклый многоугольник, координаты вершин которого известны, но совсем не обязательно заданны в порядке обхода. Банковские активы сохраняются в подвальном этаже, который представляет собой одну комнату. Подвал находится под всем помещением банка. Грабители узнали, что в том районе города, где находится банк, проходит кольцевой горизонтальный канализационный коллектор ( для неспециалистов в вопросах канализации - подземный коридор в виде круга ) и проходит он чуть-чуть глубже подвального помещения банка. Помогите грабителям, которые попали в коллектор, рассчитать минимальную длину горизонтального туннеля,  который им надо прорыть, чтобы ограбить банк. Имейте ввиду: как грабители попали в коллектор, знают только они, а вот выйти из него они могут только за пределами банка.   Авторы задачи гарантируют, что даже в случае правильного ответа Вам не будет предъявлено обвинение в содействии злоумышленникам
Технические условия. Вы вводите с клавиатуры  число вершин N, потом N пар (Xi Yi)   вещественных чисел -- координаты вершин, а после координат последней вершины - тоже  действительные  кординаты  (Xr  Yr)  центра коллектора  его радиус.R. Все числа вводятся через пробел. Ви выводите на экран одно действительное число- длину туннеля.. Вершин у многоугольника  не более 50, все координаты по модулю не перевышают 1000, а радиус коллектора не больший 500.

Пример
Ввод:   4 1 1 3 2 1 2 3 0 -3 -3 2
Вывод:  3.65685424949334E+0000

Кравець Г.П,   Непомнящий Г.І., Пасіхов Ю.Я., Порубльов І.М.


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"