eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Проводники

Проводники

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Итак, ценитель звука Вова решил отдать на доработку свою аппаратуру. Один из способов улучшить звучание - использовать навесной монтаж проводами большого сечения, также для ещё большего уменьшения сопротивления они должны быть по возможности короткими. Как соединить 2 вывода понятно, также несложно ищется оптимальный монтаж, соединяющий 3 вывода. А вот 4?

На печатной плате есть 4 вывода, которые нужно соединить между собой (между каждой парой выводов должен быть контакт). Разрешается добавить от 0 до 3 вспомогательных выводов. А также соединять выводы между собой отрезками провода. Цель - минимизировать суммарную длину проводов.

Входные данные

Первая строка содержит количество тестов n (1n100). Каждый тест состоит из 4 строк, содержащих (x[i], y[i]) координаты выводов (-200x[i], y[i]200, 1i4). Никакие две точки из четырёх не совпадают. Тесты разделены между собой пустой строкой.

Выходные данные

Для каждого теста вывести в отдельной строке минимально возможную длину провода. Число требуется вывести с не менее чем 4 десятичными знаками.

Пример

Входные данные #1
2
0 0
2 0
2 1
3 0

0 0
0 1
1 0
1 1
Выходные данные #1
3.9093
2.7321
Источник 2006 Ural SU Contest, Петрозаводск, Зима, Январь 30, Задача B