Rent-A-Pixel
Harriet T. Emmel veb saytında "daşınmaz əmlak" satır və bu, 10-dan-10 kvadrat piksel blokları şəklindədir. O, veb səhifəsini düzbucaqlı bir şəbəkəyə bölüb, şəbəkə xətləri 10 piksel aralıqdadır. Hər kəs bu şəbəkədə 10-piksel-10-piksel blokları kirayə götürərək sənət əsərləri, reklam və ya başqa bir şey yerləşdirə bilər.
Harriet gözləyirdi ki, əksər müştərilər blokların düzbucaqlı bölgələrini almaq istəyəcəklər, lakin bir neçəsi daha yaradıcı olmaq istəyir. Məsələn, bir optik eynək şəklində bloklar almaq istəyirdi və bir ox və yay şirkəti hədəf şəklində yer kirayə götürmək istəyirdi (aşağıda hər kvadrat 10-piksel-10-piksel blokdur):
Şəkil 1
Harriet qərara gəldi ki, sadəlik naminə, hər bir alış-veriş bir "ortoqonal konveks" bloklar bölgəsi olmalıdır. Bu sadəcə o deməkdir ki, bölgə ilə kəsişən hər hansı bir sıra və ya sütun piksel ya sıfır, ya da bir bağlı seqmentdən ibarət olmalıdır. Yuxarıdakı iki nümunə üçün, istənilən blokları əhatə edən ən kiçik ortoqonal konveks bölgələr bunlardır:
Şəkil 2
Müştərilərinə xidmət olaraq, H. T. Emmel onlara istənilən blok dəstini seçməyə imkan verir, sonra isə o, onları əhatə edən ən kiçik ortoqonal konveks bölgəni hesablayır. Ümumiyyətlə, bu hesablanmış bölgə əlaqəsiz ola bilər, lakin sadəlik üçün biz fərz edirik ki, o, əlaqəlidir, yəni bölgədəki hər hansı iki pikseli birləşdirən ortoqonal bir yol var. Bu ən kiçik bölgə hesablamasını edən proqramı yazın.
Giriş verilənləri
Hər test halı istifadəçi tərəfindən tələb olunan 10-piksel-10-piksel blokların sayını göstərən müsbət tam ədəd n, n ≤ 10000 olan bir sətirdən ibarət olacaq.
Bundan sonra bir və ya daha çox sətir gələcək, burada ümumilikdə 2n tam ədəd r_{0 }c_{0 }r_{1 }c_{1 }... r_{n-1 }c_{n-1}, 0 ≤ r_i, c_i ≤ 10^9. Hər r_i c_i cütü bu bloklardan birinin sol üst pikselinin sıra və sütun nömrəsini verir.
Bu koordinatların hamısı 10-un qatları olacaq və heç bir koordinat cütü test halında təkrarlanmayacaq. Hər bir test halı tək, əlaqəli, minimal, ortoqonal konveks poliqonla əhatə olunacaq. Tək 0 olan bir sətir girişi bitirəcək.
Çıxış verilənləri
Hər test halı üçün, bloklar tərəfindən təsvir olunan ən kiçik ortoqonal konveks poliqonun zirvələrinin (sıra, sütun) piksel koordinatlarını göstərən hal nömrəsini çap edin. İlk koordinat ən aşağı sıra nömrəsinə malik blok üçün olmalıdır və onların arasında ən aşağı sütun nömrəsi olmalıdır. Koordinatlar poliqonun saat əqrəbi istiqamətində keçidini təsvir etməlidir.
Qeyd: Məkan məhdudiyyətinə görə, Hal 2 üçün çıxış bir neçə sətir üzərində göstərilmişdir. Əslində, hamısı bir sətirdə olmalıdır.