Алтыbucaqlı çubuqlar#5702
Bu məsələdə sonsuz altıbucaqlı şəbəkəni nəzərdən keçiririk. Şəbəkə eyni ölçülü düzgün altıbucaqlı hüceyrələrdən ibarətdir və aşağıda təsvir olunduğu kimi düzülmüşdür. Şəkil həmçinin hər bir hüceyrəni tanımaq üçün istifadə olunan koordinat sistemini göstərir. Hər bir hüceyrə boş və ya bloklanmış ola bilər.
Şəkil: Şəbəkənin bir hissəsi
Şəbəkədə təsadüfi şəkildə bir neçə çubuq yerləşdirilib. Hər bir çubuğun uzunluğu bir "altıbucaqlı vahid"-dir, yəni çubuğun ucları qonşu hüceyrələrin mərkəzində yerləşir. Sizin vəzifəniz çubuqları elə hərəkət etdirməkdir ki, qapalı və düzgün altıbucaqlı alınsın.
Aşağıdakı şəkillərdə çubuqlardan ibarət qapalı altıbucaqlının nümunələri göstərilmişdir.
Sizə şəbəkədə yerləşdirilmiş çubuqların ilkin koordinatları təqdim olunur. Eləcə də bloklanmış hüceyrələrin koordinatları verilir. Hər bir gedişdə aşağıdakı hərəkətlərdən birini edə bilərsiniz:
Bir çubuq seçin və onu şəbəkədən çıxarın;
Bir çubuq seçin və onu uclarından birinin ətrafında 60 dərəcə saat və ya əks saat istiqamətində fırladın;
Bir çubuq seçin və onu uzunluğu qədər istiqamətində hərəkət etdirin.
Çubuqlar heç vaxt bloklanmış hüceyrədə dayanmamalıdır. Ancaq iki çubuq eyni anda eyni hüceyrədə ola bilər.
Yuxarıdakı vəziyyətdə maneə koordinatında, bir çubuq isə və nöqtələri arasındadır. Bu çubuq üçün dörd mümkün hərəkət aşağıda göstərilmişdir.
Bütün hərəkətlər tamamlandıqdan sonra yalnız qapalı düzgün altıbucaqlı formalaşmalıdır, başqa heç bir çubuq qalmamalıdır. Yəni şəbəkədə tam olaraq 6 \times x çubuq olmalıdır, burada müsbət tam ədəddir. Bunu minimum hərəkət sayı ilə əldə edə bilərsinizmi?
Birinci sətrdə (T < 50) — testlərin sayı verilir.
Hər bir testdə əvvəlcə (S < 9) — çubuqların sayı göstərilir. Sonrakı sətrdə hər bir çubuq x_1\ y_1\ x_2\ y_2 şəklində, (x_1, y_1) nöqtəsindən (x_2, y_2) nöqtəsinə qədər təsvir olunur. Bütün koordinatlar düzgündür və hər bir çubuğun uzunluğu bir altıbucaqlı vahidinə bərabərdir.
Növbəti sətrdə (B < 20) — maneələrin sayı göstərilir. Daha sonra sətrdə maneələrin koordinatları x_1\ y_1 formatında verilir. Zəmanət verilir ki, heç bir maneə çubuqlarla üst-üstə düşmür. Bütün koordinatlar (çubuqlar və maneələr) aralığında tam ədədlərdir.
Qeyd: şəbəkə sonsuzdur. Optimal nəticədə alınan altıbucaqlının koordinatları aralığından kənarda ola bilər.
Hər bir test üçün, testin nömrəsi və tələb olunan minimum hərəkət sayı çap olunmalıdır. Əgər altıbucaqlını düzəltmək mümkün deyilsə, **impossible** çıxarın. Daxil və çıxış nümunəsinin formatına tam riayət edin.
Nümunə 1