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

Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

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

F. Сигнальные костры

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Капитан Врунгель и его старший помощник Лом потерпели кораблекрушение на необитаемом острове. Пока капитан Врунгель искал в джунглях острова пресную воду, Лом решил соорудить на пляже несколько сигнальных костров. С наступлением темноты он собирался зажечь их, чтобы подать таким образом сигнал бедствия проплывающим кораблям.
Когда капитан Врунгель вернулся на пляж, Лом уже сложил там n костров. Капитан, посмотрев на костры, сказал, что если сложить все костры на одной прямой, то сигнал будет хорошо заметен не только с корабля, но и с самолёта. Найдите минимальное суммарное расстояние, на которое Лому придётся перетащить костры, чтобы они все оказались расположенными на одной прямой.

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

В первой строке записано целое число n — количество костров (2 ≤ n ≤ 1000). Далее в n строках перечислены координаты этих костров xi и yi — целые числа, по модулю не превосходящие 106.

Результат

Выведите минимальное суммарное расстояние, на которое Лом должен перетащить костры, с абсолютной или относительной погрешностью не более 10−6.

Пример

исходные данныерезультат
4
0 0
0 1
1 1
1 0
1.414214
Автор задачи: Павел Климов (подготовка — Ольга Соболева)
Источник задачи: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1956. Сигнальные костры