Divar kağızlarının yapışdırılması
Mayor Pronin mənzilində təmir işlərinə başladı və mətbəxin divarlarından birində (N–1) üfüqi və şaquli tərəfləri olan düzbucaqlı ventilyasiya dəlikləri açmalı idi (1 ≤ N ≤ 100). Əgər yeni dəlik artıq açılmış olanla kəsişirdisə, mayor yalnız toxunulmamış hissəni kəsirdi.
Təmir işlərindən sonra divara oboy yapışdırmaq lazım idi. Mayor yaxınlıqdakı mağazadan istənilən ölçüdə və sıfır olmayan sahəyə malik ən çox (2N–1)^2 düzbucaqlı oboy parçası sifariş edə bilərdi. O, divarı oboy parçaları ilə elə örtmək istəyirdi ki:
Ventilyasiya dəlikləri örtülməsin.
Heç bir iki parça bir-birini kəsməsin (onlar tərəfləri ilə toxuna bilərlər).
Divarda örtülməmiş sahə qalmasın.
Giriş verilənləri
Dekart koordinat sistemini nəzərdən keçirək, burada oxlar dəliklərin və divarın tərəflərinə paraleldir.
Əvvəlcə N (1 ≤ N ≤ 100) ədədi daxil edilir, sonra isə N düzbucaqlının təsviri verilir. Birinci düzbucaq divarın yerini təsvir edir, qalan (N–1) isə dəliklərin yaranma sırasını göstərir. Bütün düzbucaqların tərəfləri koordinat oxlarına paraleldir. Hər bir düzbucaq sol alt və sağ üst künclərinin koordinatları ilə verilir: x_1, y_1, x_2, y_2. Koordinatlar modulu 31000-dən çox olmayan tam ədədlərdir, x_1 < x_2, y_1 < y_2.
Dəliklərin yerini göstərən düzbucaqlar kəsişə və toxuna bilər, çünki bu təmir işləri zamanı lazım ola bilərdi. Aydındır ki, bütün ventilyasiya dəlikləri divarın içindədir, yəni birinci düzbucağın sərhədlərindən kənara çıxmır.
Çıxış verilənləri
Əvvəlcə mağazadan sifariş edilməli olan oboy parçalarının sayını K çıxarın (K (2N–1)^2-dən çox olmamalıdır). Sonra yapışdırma sxemini çıxarın: sifariş edilən parçaların yerləşmə yerlərini göstərən K düzbucaq. Hər bir düzbucağın sol alt və sağ üst künclərinin koordinatlarını çıxarmaq lazımdır. Bütün koordinatlar tam ədədlər olmalıdır. Həllin mövcud olduğu təmin edilir.
Əgər bir neçə mümkün üsul varsa, istənilən birini çıxarın.