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

Мережа доріг

Мережа доріг

У маленькій, але дуже гордій державі є \textbf{n} військових баз. Нещодавно король вирішив з'єднати їх дорогами так, щоб з кожної бази можна було потрапити на довільну іншу, пройшовши по одній або декільком дорогам. Цікава особливість цієї країни полягає у тому, що інженери у ній уміють будувати лише дороги, які йдуть або з півночі на південь, або з заходу на схід. Король доручив скласти план міністру транспорту, а він, у свою чергу, звалив це доручення на Вас - Верховного Програміста держави. Вам необхідно визначити, яку мінімальну сумарну довжину можуть мати дороги у збудованій мережі доріг. У країні введено декартову прямокутну систему координат, причому її вісь \textbf{Ox} йде з заходу на схід, а вісь \textbf{Oy} - з півдня на північ. Розміри баз достатньо невеликі, тому їх можна вважати точками, а дороги - відрізками на площині. \InputFile У першому рядку задано число елементів \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10}). У наступних \textbf{n} рядках розміщено самі елементи. Кожен елемент описує координати однієї бази у форматі "\textbf{x y}", де \textbf{x} - її абсциса, а \textbf{y} - її ордината, \textbf{x} і \textbf{y} - цілі числа від \textbf{-1000} до \textbf{1000} включно. \OutputFile Єдине число - десятковий запис мінімальної сумарної довжини всіх збудованих доріг, округлене рівно до \textbf{3}-х знаків після десяткової крапки за стандартними математичними правилами округлення. \textbf{Примітка} Можливі розміщення оптимальних мереж доріг для наведених в умові прикладів наведено на рисунку нижче: \includegraphics{https://static.e-olymp.com/content/3f/3f5ea69412fa425214648d310b5ebec7b646b322.jpg}
Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3
0 1
2 0
3 2
Вихідні дані #1
5.000