Mərtəbələr
Yeni avtomobil yolu A və B arasında daha yaxşı və sürətli əlaqə yaradaraq tıxacları əhəmiyyətli dərəcədə azaltmağı vəd edirdi. Təəssüf ki, bir maneə var idi: köhnə malikanə. Bu münaqişə tezliklə avtomobil yolunun xeyrinə həll edildi.
Malikanənin sökülməsinə az qalmış, köhnə malikanələrin bir həvəskarı malikanədəki rəngli kafel döşəmələrin məşhur rəssam Mondriaan tərəfindən dizayn edildiyini və buna görə də böyük mədəni dəyərə malik olduğunu öyrəndi. Onlar xilas edilməlidir. Malikanə sökülməzdən əvvəl döşəmələr malikanədən çıxarılmalıdır.
Bu işin öhdəsindən gəlmək üçün bir döşəmə daşıma mütəxəssisi işə götürüldü. O, hər bir döşəməni daha kiçik hissələrə kəsməyə qərar verdi ki, bu da onları daha asan idarə edilə bilən hala gətirirdi. O, döşəmənin düzbucaqlı hissəsini iki kiçik düzbucaqlı hissəyə kəsməyə imkan verən incə bir döşəmə kəsmə alətinə malik idi, kəsik tərəflərdən birinə paralel olmalı idi. Əlbəttə ki, kəsik kafel arasında olmalıdır; kafelin içindən keçmək mümkün deyildi. Bu şəkildə Şəkil 1-dəki döşəmə asanlıqla 9 kafelə kəsilə bilərdi. Lakin Şəkil 2-dəki döşəmə daha kiçik hissələrə kəsilə bilməz. Şəkil 3-dəki döşəmə altı hissəyə kəsilə bilər, lakin hissələrdən biri bir neçə kafeldən ibarət olacaq.
İşə hazırlaşarkən, döşəmə daşıma mütəxəssisi qalan hissələrin nə qədər böyük ola biləcəyini bilməkdən narahat idi: onlar ağır, çox ağır, yoxsa son dərəcə ağır olacaqlar? Hansı növ döşəmə qaldırma aləti icarəyə götürülməlidir? Çünki döşəmələrin sabit qalınlığı və sabit sıxlığı var, döşəmə parçasının çəkisi yalnız onun sahəsindən asılıdır.
Düzbucaqlı kafellərlə örtülmüş düzbucaqlı döşəmə verildikdə, döşəmə ən kiçik mümkün hissələrə kəsildikdən sonra ən böyük hissənin sahəsini tapın. Ən kiçik və ən böyük sözləri hissələrin sahəsinə aiddir. Kafelin içindən keçmək qadağandır. Düzbucaqlı boyunca kəsik həmişə tərəflərdən birinə paralel və tam uzunluq (və ya en) boyunca olmalıdır.
Giriş verilənləri
Giriş bir neçə döşəməni ehtiva edir. Girişin ilk sətri döşəmələrin sayını verir.
Hər bir döşəmə bir neçə sətirdə təsvir edilir. İlk sətir iki müsbət tam ədədi ehtiva edir: döşəmənin uzunluğu və eni, millimetrlə. Döşəmə ən çox 40 000 mm uzunluğunda və ya enindədir. Növbəti sətir t kafel sayını ehtiva edir (1 ≤ t ≤ 100). Növbəti t sətir hər biri bir kafelin təsvirini ehtiva edir. Kafel dörd tam ədəd kimi verilir: xl yl xh yh, burada (xl, yl) kafelin aşağı sol küncünün koordinatlarıdır və (xh, yh) kafelin yuxarı sağ küncünün koordinatlarıdır. Kafel həmişə müsbət sahəyə malikdir. Döşəmənin koordinatlarının sırası və kafelin koordinatları əlbəttə ki, üst-üstə düşür.
Kafellərin bir-birindən ayrı olduğunu və döşəməni, bütün döşəməni və yalnız döşəməni əhatə etdiyini fərz edə bilərsiniz.
Çıxış verilənləri
Hər bir test üçün (hər bir döşəmə) çıxış bir sətirdə bir rəqəm ehtiva edir: döşəmə ən kiçik mümkün hissələrə kəsildikdən sonra ən böyük döşəmə parçasının sahəsi (kvadrat millimetrlə).