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}-х знаков после десятичной точки по стандартным математическим правилам округления. \Note Возможные расположения оптимальных дорожных сетей для приведённых в условии примеров приведены на рисунке ниже: \includegraphics{https://static.e-olymp.com/content/3f/3f5ea69412fa425214648d310b5ebec7b646b322.jpg}
Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
3
0 1
2 0
3 2
Выходные данные #1
5.000