АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

573. H - Робот

Ограничение времени: 1 сек.
Ограничение памяти:128000 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Роботу нужно пройти по плоскости из точки A в точку B. Пройти по прямой не всегда возможно из-за препятствий. Требуется написать программу, вычисляющую минимальную длину пути робота из точки A в точку B. Будем считать размеры робота пренебрежимо малыми по сравнению с преодолеваемым расстоянием и размером препятствий. Будем считать, что все препятствия представлены набором отрезков на плоскости. Эти отрезки робот не может пересекать во внутренних точках, но он может проходить через концы отрезков, а также может ходить вдоль отрезка.

Время тестирования: 1 секунда на один тест.

Первая строка входного файла содержит одно целое число N — количество отрезков-препятствий (0 £ N £ 100). Затем идут N строк по четыре целых числа x1, y1, x2 и y2 в каждой. Это координаты концов соответствующего отрезка. Последние две строки содержат координаты x и y точек A и B. Гарантируется, что все координаты по модулю не превосходят 1000, а также ни один из концов отрезков не принадлежит другому отрезку. Начальная и конечная точки пути различны и не принадлежат ни одному отрезку.

Выведите в выходной файл одно число — длину кратчайшего пути из точки A в точку B с четырьмя знаками после десятичной точки. Если искомого пути не существует, то выведите –1.

Примеры

input

output

1

5 -2 5 3

10 0

0 0

10.7703

2

0 0 2 0

3 0 10 0

-100 0

100 0

200.0000

3

-1 -1 6 6

4 6 11 -1

-1 0 11 0

2 1

-100 -100

-1

 


Статистика Послать на проверку Обсуждение задачи Автор/источник: Павел Кузнецов, XI Межвузовская олимпиада, Вологда
Задачи с соревнований / Межвузовские олимпиады / XI Межвузовская олимпиада 2008 /
572. G - Хорды 573.
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.