Yol şəbəkəsi#1445
Kiçik, lakin çox qürurlu bir ölkədə hərbi baza var. Kral bu bazaları yollarla birləşdirməyə qərar verdi ki, istənilən bazadan digərinə getmək mümkün olsun, lazım gələrsə bir neçə yoldan keçməklə. Bu ölkənin maraqlı xüsusiyyəti ondadır ki, mühəndislər yalnız şimaldan cənuba və ya qərbdən şərqə doğru yollar tikə bilirlər. Kral Nəqliyyat nazirinə bu planın hazırlanmasını tapşırdı, nazir isə bu işi sizə — dövlətin Ali Proqramçısına həvalə etdi. Siz tikiləcək yol şəbəkəsində yolların ümumi minimal uzunluğunu müəyyən etməlisiniz.
Ölkədə Dekart koordinat sistemi istifadə olunur: oxu qərbdən şərqə, oxu isə cənubdan şimala doğru yönəlmişdir. Bazaların ölçüləri o qədər kiçikdir ki, onları nöqtə, yolları isə müstəvidə düz xətt parçası kimi qəbul etmək olar.
Birinci sətirdə bazaların sayı (1 \leq n \leq 10) verilir. Sonrakı sətirdə isə hər bir bazanın koordinatları "" formatında verilir. Burada abssisa, isə ordinatdır; və -dən -ə qədər tam ədədlərdir.
Bir ədəd yazın — tikiləcək yolların minimal ümumi uzunluğunu, standart yuvarlaqlaşdırma qaydalarına görə tam onluq rəqəmədək yuvarlaqlaşdırmaqla.
Nümunə 1
Yuxarıdakı nümunələr üçün mümkün optimal yol şəbəkələri aşağıdakı kimidir:
