Diplomatik münasibətlər#1046

Diplomatik münasibətlər

1 saniyə
64 meqabayt
Çox asan

Xarici işlər üçün xərcləri minimuma endirmək məqsədilə qərara alındı ki, hər bir ölkənin yalnız bir başqa ölkə ilə diplomatik əlaqə saxlaması kifayət deyil; çünki dünyada iki və ya daha çox ölkə olduqda, bəzi ölkələr diplomatlar zənciri vasitəsilə bir-biri ilə əlaqə saxlaya bilməzlər.

İndi fərz edin ki, hər bir ölkə ən çox iki başqa ölkə ilə diplomatik əlaqə saxlayır. Yazılmamış diplomatik qaydalara əsasən, hər bir ölkə bərabər şəkildə rəftar edilməlidir, ona görə də hər bir ölkə məhz iki başqa ölkə ilə diplomatik əlaqələr saxlamalıdır.

Beynəlxalq topoloqlar bu tələblərə cavab vermək üçün bir struktur təklif ediblər: ölkələri bir dairə şəklində düzün ki, hər bir ölkə sağ və sol qonşusu ilə diplomatik əlaqə saxlasın. Əslində, hər bir ölkənin diplomatik ofisi öz ölkəsində yerləşir və sadəlik üçün onun yeri ikiölçülü müstəvidə bir nöqtə kimi verilir. Əgər əlaqəli ölkələrin diplomatik ofislərini düz xətlərlə birləşdirsək, çoxbucaqlı alınacaq.

İndi isə ikitərəfli diplomatik görüşlər üçün məkanlar müəyyən edilməlidir. Diplomatik səbəblərə görə, hər iki diplomat görüş yerinə bərabər məsafə qət etməlidir. Səmərəlilik üçün isə bu məsafə mümkün qədər az olmalıdır. Bu problemi həll etməyə hazır olun!

Giriş

Girişdə bir neçə test halı var. Hər bir test halı (N \ge 3), ölkələrin sayı ilə başlayır; həmişə tək olacaq. Sonra ardıcıllıqla cüt tam ədədləri (, koordinatları, |x|, |y| < 10^{12}) verilir və bu koordinatlar diplomatik ofislərin yerləri müəyyən edir. Ölkələr verilən ardıcıllıqla düzülüb və birinci ölkə sonuncunun da qonşusudur. Giriş EOF-da bitir.

Çıxış

Hər bir test halı üçün cavabda əvvəlcə – görüş yerlərinin sayı, sonra isə hər görüş yerinin və koordinatları göstərilməlidir. Görüş yerləri ardıcıllığı girişə uyğun olmalıdır: birinci və ikinci ölkə üçün görüş yerindən başlanılıb növbə ilə davam etdirilməli, ən sonda isə -ci və birinci ölkə üçün görüş yeri göstərilməlidir. Koordinatlar onluqdan sonra dəqiqliklə verilməlidir.

Qeyd

Giriş və çıxış çoxbucaqlılar kimi şərh edilə bilər. Giriş və çıxış çoxbucaqlıların əlaqəsi 1047-ci problem üçün olan şəkildə göstərilib. Əlavə giriş nümunələrini bu məsələnin həllindən istifadə edərək yarada bilərsiniz.

Nümunələr

Nümunə 1

Loading
Loading