Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Java программирование > Общие вопросы по Java, Java SE, Kotlin
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.10.2014, 21:08   #1
Demius
Пользователь
 
Регистрация: 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
Demius вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
решение задачи Дирихле методом Гаусса-Зейделя на Паскале. Объяснить код программы 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