Yol şəbəkəsi
Kiçik ölkədə n sayda hərbi baza var. Bu yaxınlarda şah bu bazaları yollarla elə birləşdirmək qərarına gəldi ki, hər bir bazadan digərinə bir və ya bir neçə yolla getmək mümükün olsun. Bu ölkənin maraqlı xüsusiyyəti ondan ibarətdir ki, mühəndislər orda yalnız şimaldan cənuba və ya qərbdən şərqə gedən yollar sala bilirlər. Şah nəqliyyat nazırınə plan tərtib etmə tapşırığı verdi. O da öz növbəsində bi tapşırığı Sizə - dövlətin Ali Proqramçısına tapşırdı. Siz qurulan yol şəbəkəsində yolların ümumi uzunluğunun minimal qiymətini təyin etməlisiniz.
Ölkədə dekart düzbucaqlı koordinat sistemi daxil edilmişdir, burada Ox oxu qərbdən şərqə, Oy isə cənubdan şimala yönəlmişdir. Bazaların ölçülüri kifayət qədər böyük deyil, buna görə də onları nöqtələr kimi, yolları isə parçalar kimi hesab etmək olar.
Giriş verilənləri
İlk sətir bazaların n (1 ≤ n ≤ 10) sayını ehtiva edir. Növbəti n sətrin hər biri bir bazanın "x y" formatında koordinatlarını ehtiva edir, burada x absis, y isə ordinatdır, x və y -1000 -dən 1000 -ə qədər tam ədədlərdir.
Çıxış verilənləri
Yolların ümumu uzunluqlarının qiymətini onluq nöqtədən sonra 3 rəqəm dəqiqliyi ilə verməli.
Qeyd
Yuxarıda verilən nümunələrə uyğun ən yaxşı yol şəbəkəsi aşağıdakı kimidir:
