Kvadrat
Verilmiş kvadrat [0, 1]×[0, 1] daxilində N nöqtəsi (P_1, P_2, ..., P_N) yerləşir (fərqli nöqtələrin eyni mövqedə ola biləcəyini qəbul edə bilərsiniz). Biz bu N nöqtəsini və kvadratın dörd küncünü elə xətt seqmentləri ilə birləşdirməliyik ki, bu seqmentlər vasitəsilə N+4 nöqtənin istənilən ikisi bir-birinə (birbaşa və ya dolayı yolla) çata bilsin. Qraf uzunluğu xətt seqmentlərinin ümumi uzunluğu kimi təyin edilir. N nöqtələrinin mövqeləri sabit olduqda, onları birləşdirməyin elə bir yolu olmalıdır ki, bu, ən qısa qraf uzunluğunu təmin etsin. Biz bu birləşdirmə üsulundan istifadə edərək qraf uzunluğunu qeyd etmək üçün LEN (P_1, P_2, ..., P_N) istifadə edə bilərik.
Bu vəziyyətdə, LEN (P_1, P_2, ..., P_N) P_1, P_2, ..., P_N funksiyasıdır. P_1, P_2, ..., P_N mövqelərini dəyişdikdə, LEN (P_1, P_2, ..., P_N) də dəyişir. Asanlıqla sübut etmək olar ki, kvadrat daxilində elə P_1', P_2', ..., P_N' mövcuddur ki, LEN (P_1', P_2', ..., P_N') minimumdur.
N nöqtələrinin ilkin mövqeləri verildikdə, sizin vəzifəniz kvadrat daxilində elə N nöqtəsi P_1", P_2", ..., P_N" tapmaqdır ki, |P_1P_1"| + |P_2P_2"| + ... + |P_NP_N"| minimum olsun və LEN (P_1", P_2", ..., P_N") = LEN (P_1', P_2', ..., P_N'). Sizdən |P_1P_1"| + |P_2P_2"| + ... + |P_NP_N"| dəyərini çıxış etmək tələb olunur, burada |P_iP_i"| P_i və P_i" arasındakı məsafədir.
Məsələn, Şəkil-1 P_1 nöqtəsinin ilkin mövqeyini və LEN (P_1) əldə etmək üçün birləşdirmə üsulunu göstərir. Şəkil-2-də P_1" mövqeyi, kvadratın mərkəzindədir, və LEN (P_1") əldə etmək üçün birləşdirmə üsulu göstərilir. Sübut etmək olar ki, LEN (P_1") = LEN (P_1'); sizin işiniz P_1 və P_1" arasındakı məsafəni çıxış etməkdir.
Giriş verilənləri
Giriş bir neçə testdən ibarətdir. Hər bir test üçün ilk sətir bir tam ədəd N (1 ≤ N ≤ 100) nöqtələrin sayını verir və N sətir hər bir nöqtənin koordinatlarını aşağıdakı formatda verir:
x y
Burada, x və y [0, 1] dəyər aralığında olan onluq ədədlərdir.
N = 0 olan test girişi sonu göstərir və işlənməməlidir.
Çıxış verilənləri
Hər bir test üçün |P_1P_1"| + |P_2P_2"| + ... + |P_NP_N"| dəyərini çıxış edin. Dəyər ondalıqdan sonra üç rəqəmə yuvarlanmalıdır.