Kart plitələri
Kartların çapı mürəkkəb bir məsələdir. Əvvəlcə, sferik Yer kürəsinin xəritəsini müstəviyə yerləşdirmək üçün uyğun çevrilməni tapmaq lazımdır. Daha sonra, yüksək keyfiyyətli xəritələrin çapı üçün bir neçə vərəq kağızdan istifadə etmək lazım gəlir, çünki onlar bir vərəqə sığmır. Bu çətinliyi aradan qaldırmaq üçün xəritə nəşriyyatçıları xəritəni bir neçə düzbucaqlı hissəyə bölür və hər hissəni ayrı-ayrılıqda çap edirlər. Bu məsələdə siz də bu prosesdə iştirak edəcəksiniz.
Beynəlxalq Xəritə Nəşriyyatçıları Assosiasiyası xəritələrin çap xərclərini azaltmağa çalışır. Onlar istifadə olunan ayrı vərəqlərin sayını minimuma endirərək xəritələrin çapını optimallaşdırmağa çalışırlar. Hətta standart vərəq ölçüsü və xəritə miqyası ilə belə, onların yerləşdirilməsini tənzimləməklə vərəq xərclərini optimallaşdırmaq mümkündür.
Şəkilin sol tərəfində sahəni əhatə edən 14 vərəq göstərilmişdir. Sağ tərəfdə isə eyni sahənin, sahənin istiqamətini, vərəq ölçüsünü və miqyasını dəyişmədən, cəmi 10 vərəqlə necə əhatə oluna biləcəyi göstərilmişdir.
Şəkil: Texası vərəqlərə bölməyin iki fərqli yolu
Sizin vəzifəniz - Beynəlxalq Xəritə Nəşriyyatçıları Assosiasiyasına verilmiş sahəni əhatə etmək üçün lazım olan minimum vərəq sayını tapmağa kömək etməkdir. Sadələşdirmək üçün sahə öz-özünə kəsişməyən qapalı çoxbucaqlıdır.
Qeyd edək ki, bütün vərəqlər üfüqi və şaquli ilə paralel tərəfləri olan fasiləsiz bir şəbəkənin hissələri olmalıdır. Vərəqlər yalnız tam tərəfləri ilə toxuna bilər və döndərilə bilməz. Bundan əlavə, bütün verilmiş koordinatlar tam ədədlər olsa da, vərəqlər qeyri-tam ədədi koordinatlarda yerləşdirilə bilər.
Çoxbucaq vərəqlərin tərəflərinə toxuna bilər (məsələn, 2 nümunəsində olduğu kimi). Lakin, rasional ədədlərin maşın təqdimatı ilə bağlı problemlərdən qaçmaq üçün, çoxbucağın zirvəsinin vərəqdən 10^{-6} məsafədə kənarda yerləşməsi halında cavabın dəyişməyəcəyini qəbul etmək olar.
Giriş verilənləri
Giriş məlumatları bir testdən ibarətdir. Testin ilk sətirində üç ədəd n, x_s və y_s yazılmışdır. Çoxbucağın zirvələrinin sayı n (3 ≤ n ≤ 50), xəritəni əhatə etmək üçün lazım olan vərəqlərin ölçüləri x_s və y_s (1 ≤ x_s, y_s ≤ 100). Növbəti n sətirin hər biri çoxbucağın zirvəsini təsvir edən iki tam ədəd x və y (0 ≤ x ≤ 10x_s, 0 ≤ y ≤ 10y_s) ehtiva edir (saat əqrəbi istiqamətində və ya əksinə).
Çıxış verilənləri
Çoxbucağı əhatə etmək üçün lazım olan minimum vərəq sayını çıxarın.