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

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

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

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

Капитан Врунгель и его старший помощник Лом потерпели кораблекрушение на необитаемом острове. Пока капитан Врунгель искал в джунглях острова пресную воду, Лом решил соорудить на пляже несколько сигнальных костров. С наступлением темноты он собирался зажечь их, чтобы подать таким образом сигнал бедствия проплывающим кораблям.

Когда капитан Врунгель вернулся на пляж, Лом уже сложил там n костров. Капитан, посмотрев на костры, сказал, что если сложить все костры на одной прямой, то сигнал будет хорошо заметен не только с корабля, но и с самолёта. Найдите минимальное суммарное расстояние, на которое Лому придётся перетащить костры, чтобы они все оказались расположенными на одной прямой.

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

В первой строке записано количество костров n (2 n 1000). Далее в n строках перечислены координаты этих костров x_i и y_i (-10^6x_i, y_i10^6).

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

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

Пример

Входные данные #1
4
0 0
0 1
1 1
1 0
Выходные данные #1
1.4142135624
Автор П.Климов, О.Соболева
Источник 2013 Петрозаводск, Зима, Контест Уральского университета, Кубок Контура, Задача F