Sehrli Plitələri Silmək
Ayimok adlı sehrbazın gündəlik vəzifəsi sehrli plitələri bir sıra halında düzəltmək və sonra sehrli bir dua oxumaqdır.
Sehrli plitələr və onların düzülüşü aşağıdakı qaydalara əsaslanır:
Hər sehrli plitə 1 hündürlüyündə trapezoid formasındadır.
Bəzi plitələr digər plitələrlə üst-üstə düşə bilər.
Plitələr 2D koordinat sistemində yerləşdirilir.
Plitələrin üst kənarı y koordinatı 1 olan üfüqi xətt üzərindədir.
Plitələrin alt kənarı y koordinatı 0 olan üfüqi xətt üzərindədir.
Ayimok, sehrli duanı oxuduqdan sonra plitələri çıxarmalıdır. Bir gün, çox sayda plitəni çıxarmağın yorucu olduğunu gördü və bu prosesi sadələşdirmək qərarına gəldi.
O, plitələri səmərəli şəkildə çıxarmaq üçün "Maqnetizasiya Duası"nı öyrəndi. Bu dua, bir dəfəyə bir sıra plitələri çıxarır. Dəstdəki hər iki plitə cütü bir-biri ilə üst-üstə düşməlidir.
Məsələn, Şəkil 1-də, üç plitənin hamısına Maqnetizasiya Duası oxuyaraq onları bir dəfəyə çıxara bilər, çünki hamısı bir-biri ilə üst-üstə düşür. (Qeyd: Plitələrin hündürlükləri daha asan başa düşülməsi üçün qəsdən dəyişdirilmişdir.)
Şəkil 1: Bir dəfəyə çıxarıla bilən plitələr dəsti
Lakin, Şəkil 2-də, üç plitənin hamısına bir dəfəyə dua oxuya bilməz, çünki plitə 1 və plitə 3 üst-üstə düşmür.
Şəkil 2: Bir dəfəyə çıxarıla BİLMƏYƏN plitələr dəsti
Ayimok, plitələrin hamısını minimum sayda Maqnetizasiya Duası ilə çıxarmaq istəyir, çünki dua oxumaq çoxlu sehr gücü tələb edir.
Şəkil 3 vəziyyətini nəzərdən keçirək. O, plitələrin hamısını üç dəfə dua oxuyaraq çıxara bilər; birinci dua plitə 1 və 2 üçün, ikinci dua plitə 3 və 4 üçün, üçüncü dua plitə 5 və 6 üçün.
Şəkil 3: Bütün plitələri çıxarmağın bir yolu (oxunan duaların minimum sayı DEYİL)
Əslində, o, plitələrin hamısını cəmi iki dəfə dua oxuyaraq çıxara bilər; birinci dua plitə 1, 2 və 3 üçün, ikinci dua plitə 4, 5 və 6 üçün. Bu, plitələri çıxarmaq üçün tələb olunan minimum dua sayıdır.
Şəkil 4: Bütün plitələri çıxarmağın optimal yolu (oxunan duaların minimum sayı)
Verilən plitələr dəsti üçün, sizin vəzifəniz bu plitələrin hamısını çıxarmaq üçün Maqnetizasiya Duası oxumağın minimum sayını tapacaq bir proqram yazmaqdır.
Başqa plitələrlə üst-üstə düşməyən plitə ola bilər, lakin onu çıxarmaq üçün yenə də Maqnetizasiya Duası oxumaq lazımdır.
Giriş verilənləri
Giriş aşağıdakı formatdadır:
N
xLower_11 xLower_12 xUpper_11 xUpper_12
xLower_21 xLower_22 xUpper_21 xUpper_22
xLower_31 xLower_32 xUpper_31 xUpper_32
...
xLower_N1 xLower_N2 xUpper_N1 xUpper_N2
Birinci sətir N tam ədədini ehtiva edir, bu, plitələrin sayını göstərir.
Sonra, plitələrin məlumatlarını ehtiva edən N sətir gəlir.
(i+1)-ci sətir i-ci plitənin künc nöqtələrinin (xLower_i1, 0), (xLower_i2, 0), (xUpper_i1, 1), (xUpper_i2, 1) koordinatlarında yerləşdiyini göstərən dörd tam ədəd xLower_i1, xLower_i2, xUpper_i1 və xUpper_i2 ehtiva edir.
Heç bir iki plitənin künc nöqtələrinin üst-üstə düşməyəcəyini qəbul edə bilərsiniz. Yəni, bütün xLowerij fərqlidir və bütün xUpperij də fərqlidir. Giriş aşağıdakı məhdudiyyətlərə uyğundur:
1 ≤ N ≤ 10^5
1 ≤ xLower_i1 < xLower_i2 ≤ 10^9
1 ≤ xUpper_i1 < xUpper_i2 ≤ 10^9
Bütün xLower_ij fərqlidir.
Bütün xUpper_ij fərqlidir.
Çıxış verilənləri
Proqramınız bütün plitələri çıxarmaq üçün tələb olunan Maqnetizasiya Duası oxumağın minimum sayını çıxış etməlidir.