Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача F. Сон купца Хасана.

Задачу добавил: alef

Успешно сдано решений: 21

Друзья Елисея отправились к Ормусу, а Лисандер тем временем разыскал купца Хасана. И купец поведал ему, почему он так спешно покинул Тридевятое царство. Под вечер он уснул, и увидел страшный сон. Будто стоял он посреди пустыни, и горели перед ним два факела, а позади один. И услышал он голос - "Ты обещал носить перстень, не снимая, и нарушил обещание! Что ж, каждый получит, что хотел!" В тот же миг словно огненная нить протянулась от факела к факелу, и он очутился внутри пылающего треугольника. Купец попытался вырваться из него, но стоило ему переступить огненную нить, как на этом месте возникал новый факел, Хасана отбрасывало внутрь на прежнее место, а нить уже проходила еще и через новый факел. Купец метался из стороны в сторону, но вырваться из образовывашегося многоугольника не мог. Обессилев, он упал на песок и... проснулся.  
Сразу же отдал он приказ каравану собираться и покинуть тридевятое царство, чтобы не навлечь на него беды...
Ваша задача - вычислить, какой длины огненная нить окружила купца Хасана.
 
Формат входного файла input.txt
Первая строка - шесть целых чисел через пробел - XF1, YF1, XF2, YF2, XF3, YF3 - координаты первых трех факелов.
Вторая строка - целое число N (0 <= N <= 5000)  - количество шагов купца Хасана
Третья строка - целые числа X0, Y0 - координаты точки, в которой находится купец в самом начале.
Каждая из следующих N строк содержит пару чисел Xj, Yj (j = 1, 2, ..., N) - координаты очередной точки, в которую сделал шаг купец Хасан.
Все координаты находятся в диапазоне от -10000 до 10000
Новый факел образуется в том случае, если купец своим шагом пересекает существующую на данный момент огненную нить. Купца отбрасывает в ту точку, из которой он совершал последний шаг.
Гарантируется, что никакой очередной шаг не совершается в точку, принадлежащую нити, не проходит через точку, в которой уже стоит факел, и не приводит к пересечению нити более одного раза, а также что в результате шагов не будет происходить самопересечений нити.
 
Формат выходного файла output.txt
Первая строка - вещественное число L с точностью 6 знаков после запятой - длина образовавшейся огненной нити.
 
Пример входного файла
0 0 1 2 2 0
5
1 1
1 -2
1 -1
2 -2
3 -1
3 -2
 
Пример выходного файла
11.122417

Сдать задачу

Задать вопрос жюри по этой задаче