Təmizliyin təmin edilməsi#3573
Böyük döyüşü xatırlayırsınızmı, Halk və İyrənclik Manhetten binalarının üzərindən bir-birini atdığı vaxtı? Yaxud da Yaşıl Goblinin Hörümçək Adamı bir neçə kərpic divarına çırpdığı anı? Bu divarlar milyonlarla parça olmalı idi!
Superqəhrəmanlarımızın cinayətkarları cəzalandırması əladır, amma heç düşündünüzmü, bu ziyanı kim bərpa edir? Siz təmizləmə korporasiyasının prezidentisiniz və sizin vəzifəniz də məhz budur! Böyük döyüşdən sonra divarların bütün parçalarını toplayıb onları əvvəlki vəziyyətinə qaytarmalısınız.
Şəkil 1: Divar çoxlu parçalara bölünmüşdür
Divar, üzərinə cinayətkar atıldıqda üçbucaq parçalarına bölünən düzbucaqlı bir sahədir (bax Şəkil 1). Çətin vizual analiz apararaq, hər bir kiçik parçanın hansı ilkin struktura aid olduğunu müəyyən etdiniz. Əslində, yuxarıdakı şəkildəki kimi bir planınız var. Bundan əlavə, iki parça yan-yana olduqda, onları ayıran çatın (kənarın) bütün uzunluğu boyunca getdiklərini gördünüz, Şəkil 2a-da göstərildiyi kimi.
Şəkil 2: Yaxşı, pis və dəhşətli.
Sizin divarı bərpa etməkdə kömək edən bir robotunuz var. Robot yalnız bir dəfə bir parça endirə bilər, yuxarıdan aşağıya. Robot parçanı bir yerdən başqa bir yerə köçürə və ya onu fırlada bilmir. Robotun qırılmış parçaları toplamaq üçün əmrlərin sırasını diqqətlə tərtib etmək lazımdır ki, təsadüfən uyğun parçanın endiriləcəyi yeri bloklamasın (bax Şəkil 2d). Divarı tamamilə bərpa etmək üçün parçaların yığılma sırasını göstərə bilərsinizmi?
Birinci sətirdə bərpa etməli olduğunuz divarların sayı göstərilir. Hər bir divar üçün ilk rəqəm n (2 ≤ n ≤ 1000000) onun bölündüyü üçbucaq parçalarının sayını göstərir. Sonra n sətir gəlir, hər biri altı tam ədəd x_1 y_1 x_2 y_2 x_3 y_3 - üçbucağın üç zirvəsinin Dekart koordinatları (x, y) olan divarın bir parçasını təsvir edir. Birinci sətir parça 1-i, növbəti parça 2-ni və s. təsvir edir. Üç nöqtə həmişə saat əqrəbi istiqamətinin əksinə verilir və həmişə sıfır olmayan sahəsi olan üçbucaq təşkil edir. Bütün koordinatlar 0 ilə 10^9 daxil olmaqla dəyişir, burada y oxunun müsbət istiqaməti "yuxarı" istiqamətini göstərir. Verilən n parçalar həmişə və tamamilə düzbucaqlı sahəni əhatə edir, boşluqlar və üst-üstə düşmələr olmadan.
Hər bir divar üçün robotun divarı bərpa etmək üçün parçaları toplayacağı sırada parça nömrələrini bir sətirdə çıxarın. Əgər bir neçə belə ardıcıllıq varsa, onlardan hər hansı birini çıxarın.
Nümunə 1