Задача 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
Кравець Г.П, Непомнящий Г.І., Пасіхов Ю.Я., Порубльов І.М.
|