Windows Çizimi
Andrew FTN texnologiya şəbəkələri üçün portativ poçt proqramı KittenMail hazırlayır. Bu proqram, Norton üslubunda olan mətn rejimli pəncərə interfeysindən istifadə edir.
İndi Andrew, məşhur yeni əməliyyat sistemi Mycrowslowed Widows Not-Tested 0.4 üçün bu poçt proqramının bir versiyasını yaratmaq istəyir. Bu iş asandır, çünki proqramda sistemdən asılı olan çox az kod var. Lakin pəncərə alt sistemi ekran bufer funksiyalarına sistemdən asılı olmayan interfeys təmin edən modul üzərində qurulub.
Andrew Mycrowslowed Widows üçün pəncərə buferinin məzmununu ekranda göstərən sadə bir kod yazdı. Bu iş asan idi, çünki funksiyalar digər əməliyyat sistemlərindəki kimi idi. Lakin poçt proqramını işə salanda çox təəccübləndi! Ekranı təmizləmək təxminən bir saniyə çəkirdi! Oops... Nə səhvdir?
Andrew bu problemi araşdırmağa başladı. Bir neçə dəqiqə sonra, ekran buferinə çıxış edən hər hansı bir Mycrowslowed Widows sistem çağırışının çox vaxt apardığını kəşf etdi — 1/6000 saniyə və ya daha çox. Bu çox dəhşətlidir! O nə edə bilər?
Saatlarla düşündükdən sonra, Andrew koduna bəzi təkmilləşdirmələr etməyə qərar verdi. İndi o, ardıcıl olaraq yalnız bir simvol göstərən çağırışlar əvəzinə simvolların düzbucağını çəkən Widows-spesifik funksiyadan istifadə etmək istəyir. Onlar digər əməliyyat sistemlərində mükəmməl işləyir, lakin Mycrowslowed Widows altında çox yavaşdır. Aydın bir vəzifə ortaya çıxdı. Pəncərəni yenidən çəkən prosedur, görünən hissələrini mümkün olan ən az sayda üst-üstə düşməyən əməliyyatlarla göstərməlidir.
Sizin vəzifəniz pəncərənin bir görünən hissəsi üçün müvafiq kodu yazmaqdır. Düzbucaqlı pəncərənin bir hissəsi verildikdə, bu hissəni əhatə edən üst-üstə düşməyən düzbucaqlıların minimal sayını müəyyən edən və əhatə etmənin optimal yolunu tapan bir proqram yazın.
Giriş verilənləri
Pəncərənin görünən hissəsi yalnız tam ədədi koordinatlarla üfüqi və şaquli seqmentlərdən ibarət olan kənarı ilə verilir. Hissə deşiklər içərmir və kənarı özünü kəsmir və ya toxunmur. Hər bir seqmentin uzunluğu ən azı bir simvoldur.
Girişin ilk sətri görünən hissənin kənarındakı zirvələrin sayı n-i ehtiva edir. Növbəti n sətir zirvələrin koordinatlarını əks istiqamətdə (y koordinatları ekranda aşağıya doğru artır) ehtiva edir.
Girişdə üfüqi və şaquli seqmentlər növbələşir. Son seqment sonuncu və birinci zirvələr arasında çəkilir. n 400-ü keçmir və koordinatların mütləq dəyərləri 200-ə qədər məhdudlaşdırılır.
Çıxış verilənləri
Birinci sətirdə m — pəncərənin görünən hissəsini əhatə edən düzbucaqlı bölgələrin minimal sayı çıxarılmalıdır.
Növbəti m sətir hər biri bir düzbucaqlı təsviri ehtiva etməlidir. Düzbucaqlı dörd rəqəmlə göstərilir: minimal x, minimal y, maksimal x və maksimal y.
Əgər bir neçə optimal həll varsa, onlardan hər hansı birini çıxarın.