Yupiterian zərgərlər
"' Yupiter planeti öz zərgərləri ilə məşhurdur. Bütün Günəş sistemində ən qiymətli sayılan düz bəzəklər, qızıldan hazırlanmış körpülərlə birləşdirilmiş almaz dəstləridir. Körpü, iki qiymətli daşı birləşdirən düz bir tel parçasıdır. Gözəl bir bəzək bütövdür, yəni almazları elə bölmək olmaz ki, körpülərdən heç biri müxtəlif hissələrdəki daşları birləşdirməsin.
Mövcud ənənəyə görə, hər bir bəzəyə üç qulaqlı bir markalı zümrüd əlavə olunur, hər qulağa bir qızıl körpü bağlanır. Beləliklə, zümrüd, məsələn, iki və ya üç istənilən almazı bir-birinə bağlamağa imkan verir. Yupiterli Faberge həmişə zümrüdünü bəzəyin mərkəzinə yerləşdirir, yupiterli Leonardo isə sol alt küncə yaxınlaşdırır. Lakin bu zümrüdlər yalnız markalı bir işarə deyil, həm də qızıldan qənaət etmək imkanıdır, buna görə də ən hiyləgər və maraqlı zərgərlər qiymətli metalın xərclərini azaltmaq üçün daşlarını elə yerləşdirirlər ki, qızılın istifadəsi azalsın. Ustaların zümrüdləri çoxdur, buna görə də onların pulsuz olduğunu düşünmək olar. Bəzən, zümrüd əlavə etmək qızıl üçün əlavə xərclər tələb edərsə və ya heç bir fayda gətirməzsə, zərgərlər şöhrətdən imtina edərək markalı daşsız keçinirlər.
Yupiterin baş naziri hər gün saray zərgərlərindən sevgilisi üçün yeni bir bəzək hazırlamağı tələb edir. Bəzəklərin təkrarlanmaması üçün adətən özü onların formasını düşünür, yəni işə başlamazdan əvvəl zərgərin bütün daşların yerləşmə planı var. Son zamanlarda baş nazirə elə gəldi ki, qızıl çox sərf olunur və o, yeni baş saray zərgərini işə götürmək istəyir. Köhnə usta yerini itirmək istəmir, buna görə də sizdən ona kömək etməyinizi və bəzək hazırlamaq üçün optimal bir sxem hazırlamağınızı xahiş edir (yəni qızıl telin ən az istifadə olunduğu bir sxem).
Giriş verilənləri
Birinci sətirdə baş nazirin hazırlamağı tələb etdiyi bəzəkdəki almazların sayı olan N tam ədədi daxil edilir. Növbəti N sətirdə almazların plan üzrə koordinatları verilir - hər sətirdə iki ədəd, boşluqla ayrılmış.
Bütün testlərdə koordinatlar tamdır və modulu 10^4-dən çox deyil. Almazların sayı N 250-dən çox deyil.
Çıxış verilənləri
Birinci sətirdə optimal planda qızıl telin ümumi uzunluğunu göstərən bir real ədəd çıxarın.
Növbəti sətirdə almazın koordinatlarını göstərən iki real ədəd çıxarın. Növbəti sətirdə zümrüdlə birləşdirilmiş almazların sayı olan K ədədini, sonra isə onların nömrələrini göstərən K ədədini çıxarın. Nömrələr təkrarlanmamalıdır. Əgər optimal sətirdə zümrüd yoxdursa, K sıfıra bərabər olmalıdır və koordinatlar istənilən ola bilər. Beləliklə, K 0, 2 və ya 3 ola bilər.
Növbəti sətirdə almazları birləşdirən körpülərin sayı olan M ədədini çıxarın. Növbəti M sətirdə körpünün birləşdirdiyi almazların nömrələrini göstərən iki ədəd çıxarın.
Almazlar 1-dən N-ə qədər nömrələnir.
Əgər doğru cavablar bir neçədirsə, istənilənini çıxarın.
Cavabınız doğru cavabla 10^{-6} dəqiqliklə müqayisə olunacaq. "'