ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Пахом и овраг

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Пахом стоит в точке S и хочет как можно скорее добраться в точку T, чтобы там купить себе землю. Однако он увидел овраг, представляющий собой ломаную ABC. Какой минимальный путь придётся преодолеть Пахому, если он не хочет провалиться в овраг?
Problem illustration

Исходные данные

В первой строке записано количество тестов n (1 ≤ n ≤ 5000). В каждой из следующих n строк описывается один тест. Каждый тест представляет собой 10 целых чисел, записанных через пробел: xS, yS, xT, yT, xA, yA, xB, yB, xC, yC, являющихся координатами точек S, T, A, B и C соответственно. Все точки в тесте различны. Точки S и T не принадлежат ломаной ABC. Все координаты не превосходят по модулю 10.

Результат

Для каждого теста выведите ответ в отдельной строке, с точностью не менее 10−6.

Пример

исходные данныерезультат
3
1 2 5 6 4 4 5 2 1 6
2 2 4 3 1 3 3 3 3 1
2 1 4 4 3 2 4 3 1 4
8.000000
3.650282
3.828427
Автор задачи: Пётр Лежанкин
Источник задачи: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1750. Пахом и овраг