eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 4 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
4
0 0
0 1
1 1
1 0
Çıxış verilənləri #1
1.4142135624
Müəllif П.Климов, О.Соболева
Mənbə 2013 Петрозаводск, Зима, Контест Уральского университета, Кубок Контура, Задача F