Diplomatik münasibətlər
Xarici İşlər Naziri xərcləri minimuma endirmək üçün belə bir qərara gəldi: Hər bir ölkənin yalnız bir başqa ölkə ilə diplomatik əlaqə saxlaması kifayət deyil. Dünyada ikidən çox ölkə olduğu üçün bəzi ölkələr diplomatlar şəbəkəsi vasitəsilə bir-biri ilə əlaqə qura bilməyəcək.
İndi, hər bir ölkənin ən çox iki başqa ölkə ilə diplomatik əlaqə saxladığını fərz edək. Yazılmamış diplomatik qanunlara görə, hər bir ölkə digər ölkələrə nisbətən bərabərhüquqlu sayılır. Bu, hər bir ölkənin dəqiq iki başqa ölkə ilə diplomatik əlaqə saxladığını göstərir.
Beynəlxalq topoloqlar bu tələblərə cavab verən bir struktur təklif etdilər: Ölkələr dairə əmələ gətirsin və hər bir ölkə sol və sağ qonşusu ilə diplomatik əlaqə saxlasın. Real dünyada xarici işlər nazirliyi hər bir ölkənin daxilində yerləşir. Sadəlik üçün onun yerini ikiölçülü müstəvidə başlanğıc nöqtəsi kimi qəbul edək. Əgər müvafiq ölkələrin xarici diplomatik nümayəndəliklərinin əlaqələrini birbaşa birləşdirsəniz, nəticə çoxbucaqlı olacaq.
Hazırda ikitərəfli diplomatik görüşlər üçün yerlər yaratmaq lazımdır. Yenə də diplomatik səbəblərə görə hər iki diplomat görüş yerinə eyni məsafəni qət etməlidir. Həmçinin, səmərəlilik baxımından belə bir səyahətin məsafəsi minimuma endirilməlidir. Bu məsələnin həllinə hazır olun!
Giriş verilənləri
Giriş məlumatları bir neçə test halını ehtiva edir. Hər bir test iştirakçı ölkələrin sayını göstərən N ədədi ilə başlayır. N ≥ 3 və tək ədəd olduğunu qəbul etmək olar. Sonra N cüt x və y koordinatları gəlir ki, bunlar xarici işlər nazirliklərinin yerlərini göstərir. Xarici işlər nazirliklərinin koordinatları tam ədədlərdir və onların mütləq dəyəri 10^12-dən kiçikdir. Ölkələr giriş məlumatlarında göründükləri sırayla yerləşdirilib. Bundan əlavə, siyahıdakı ilk ölkə sonuncu ölkənin qonşusudur. Giriş məlumatları faylın sonu ilə tamamlanır.
Çıxış verilənləri
Hər bir giriş məlumatı üçün görüş yerlərinin N sayını və sonra onların x və y koordinatlarını çıxarın. Görüş yerlərinin sırası giriş məlumatlarında göstərildiyi kimi olmalıdır. İlk iki ölkə üçün görüş yerindən başlayın və beləliklə son iki ölkəyə qədər davam edin. Çıxış məlumatlarında sonuncu N-ci və birinci ölkə üçün görüş yerinin təsviri olmalıdır. Koordinatları ondalık nöqtədən sonra 6 rəqəm dəqiqliyi ilə çıxarın.
Qeyd
Qeyd edin ki, giriş və çıxış məlumatları çoxbucaqlı kimi şərh edilə bilər. Giriş və çıxış çoxbucaqlı nümunələri arasındakı əlaqə 1047-ci məsələnin şəklində göstərilmişdir. Bu məsələnin həllinə dair nümunələrinizdən istifadə edərək belə bir nümunə yaratmaq üçün əlavə nümunələr yarada bilərsiniz.