|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.10.2014, 21:08 | #1 |
Пользователь
Регистрация: 03.12.2012
Сообщений: 24
|
Прошу объяснить решение [java]
Уважаемые дамы и господа!
Во время подготовки к одной олимпиаде, я наткнулся на такую задачку: Хотя инспектор Лестрейд не отличается выдающимися дедуктивными способностями, он в совершенстве овладел всеми деталями рутинной полицейской работы. Как ни странно, многие стандартные процедуры могут нести в себе загадку, достойную не меньшего внимания, чем само преступление. Однажды вечером инспектор прибыл на место преступления - огороженный забором пустырь. Инспектор заметил, что пустырь представлял собой выпуклый многоугольник, в вершинах которого стояли столбы. По всей видимости, раньше между каждыми двумя столбами, стоящими в смежных вершинах многоугольника, существовала секция забора, ограждавшего пустырь. Однако, время неумолимо, и некоторые секции забора исчезли в неизвестных направлениях. Инспектор заметил, что у любой исчезнувшей секции забора обязательно присутствуют секции, смежные с ней. Затем Лестрейд приступил к ограждению места преступления полицейской лентой. Тут он обнаружил крайне неприятное обстоятельство: у него осталось только l метров ленты. Инспектор считает, что ленту не стоит резать на несколько кусков, и что она должна находиться только по периметру пустыря. Это означает, что инспектор зафиксирует в какой-то точке на границе пустыря один из концов ленты, после чего пройдет вдоль границы пустыря l метров в одном из двух вохможных направлений, после чего зафиксирует второй конец ленты в той точке, где окажется в тот момент. Понятно, что вся пройденная им часть границы пустыря окажется закрыта лентой, а вся остальная часть - нет. Теперь Лестрейд хочет знать, какую минимальную длину границы пустыря, не закрытую секциями забора, ему не удастся закрыть и лентой. Помогите ему, ведь до прибытия на место преступления Шерлока Холмса осталось совсем немного времени. Входные данные: В первой строке входного файла содержится три целых числа n, l и k (3 <= n <= 10^5, 0 <= l <= 10^18, 0 <= k <= n/2) - количество вершин многоугольника, который представляет собой пустырь, длина ленты инспектора и количество дыр в заборе. В следующей строке находится k целых чисел a_i (1 <= a_i <= n, a_i < a_(i+1)), описывающие отсутствующие стороны многоугольника. Каждому a_i соответствует отсутствие стороны между вершинами с номерами a_i и a_i mod n + 1. Гарантируется, что нет двух подряд идущих отсутствующих сторон. В следующих n строках находится по два целых числа x_i и y_i (|x_i| <= 10^18, |y_i| <= 10^18) - координаты i-й вершины. Вершины заданы в порядке одного из двух возможных обходов многоугольника. Описание выходного файла В выходной файл выведите одно вещественное число - минимальную суммарную длину дыр в заборе, которые не удастся закрыть лентой. Ответ будет считаться правильным, если если он отличается от правильного не более, чем на p * 10^-6, где p - периметр многоугольника. Пример входных данных 6 4 3 1 3 5 0 0 3 0 4 1 3 2 0 2 -1 1 Пример выходных данных 2.8284271 С вычислительной геометрией у меня дела плохи. Так я и не смог решить задачку. И вот недавно я нашёл решение данной задачи. Но не совсем его понимаю. Прошу вас, объясните его, пожалуйста. crimescene_ats.zip |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
решение задачи Дирихле методом Гаусса-Зейделя на Паскале. Объяснить код программы | AleSanchez | Помощь студентам | 0 | 23.09.2013 18:18 |
Прошу объяснить. | Gtnz8 | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 5 | 29.06.2013 08:06 |
Разбор задач, прошу объяснить. | AlexMasolev1992 | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 29.11.2012 17:12 |
прошу объяснить почему не работает регуляр | frommars | PHP | 2 | 07.05.2012 11:12 |
Объяснить решение заданий в Паскале | Novenkaja | Помощь студентам | 8 | 15.01.2011 19:49 |