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

Ural SU contest. Petrozavodsk training camp. Winter 2006

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

B. Проводники

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Итак, ценитель звука Вова решил отдать на доработку свою аппаратуру. Один из способов улучшить звучание — использовать навесной монтаж проводами большого сечения, также для ещё большего уменьшения сопротивления они должны быть по возможности короткими. Как соединить 2 вывода понятно, также несложно ищется оптимальный монтаж, соединяющий 3 вывода. А вот 4?
На печатной плате есть 4 вывода, которые нужно соединить между собой (между каждой парой выводов должен быть контакт). Разрешается добавить от 0 до 3 вспомогательных выводов. А также соединять выводы между собой отрезками провода. Цель — минимизировать суммарную длину проводов.

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

N – число тестов
x1 y1  первый тест
x2 y2 
x3 y3
x4 y4

x1 y1 второй тест
x2 y2
x3 y3
x4 y4
…
1 ≤ N ≤ 100. xi, yi — целые, −200 ≤ xi, yi ≤ 200, никакие две точки из четырёх не совпадают.

Результат

На каждый тест нужно вывести по одной строке, содержащей минимально возможную длину провода. Число требуется вывести не менее чем с 4 цифрами после десятичной точки.

Пример

исходные данныерезультат
2
0 0
2 0
2 1
3 0

0 0
0 1
1 0
1 1
3.9093
2.7321
Автор задачи: Дмитрий Иванков
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1460. Проводники