EduBrick

B. День объединения

1000 мс · 256 МБ · всё или ничего

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

Формат ввода

В первой строке nn (1≤n≤50001 \le n \le 5000). В каждой из следующих nn строк — целые xix_i и yiy_i (−1000≤xi,yi≤1000-1000 \le x_i, y_i \le 1000). Никакие два города не совпадают.

Формат вывода

Выведите минимальную суммарную длину дорог. Ответ принимается с точностью 10−610^{-6}.

Примеры

ввод
1
0 0
вывод
0.000000
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.