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

1815. Ферма в Сан-Андреасе

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Правительства городов Лос-Сантос, Сан-Фиерро и Лас-Вентурас, расположенных в штате Сан-Андреас, решили построить общую ферму. Жители Лос-Сантоса заявили, что будут ездить на ферму только на метро, жители Сан-Фиерро — только на автомобиле, а жители Лас-Вентураса — только на электричке.
Известна сумма, которую необходимо потратить на строительство километра линии метро, километра автомагистрали и километра железнодорожных путей. Помогите выбрать место для фермы таким образом, чтобы потратить на строительство дорог всех типов как можно меньшую сумму.

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

В первой строке записано число t (1 ≤ t ≤ 104) — количество тестов. Каждый тест состоит из четырёх строк. В первой строке записаны координаты Лос-Сантоса, во второй — Сан-Фиерро, а в третьей — Лас-Вентураса. Все координаты целые, даны в километрах и не превосходят по модулю 1000. В четвёртой строке записаны стоимости строительства километра линии метро, автомагистрали и железной дороги. Эти стоимости целые, положительные, и не превосходят 1000.

Результат

Для каждого теста выведите в отдельной строке минимальную сумму, которую придётся потратить на строительство дорог всех типов, с абсолютной или относительной погрешностью не более 10−9.

Пример

исходные данныерезультат
2
0 0
1 0
0 1
1 1 1
-3 0
3 5
0 -1
7 9 8
1.9318516526
81.1600672826
Источник задачи: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010