Kart plitələri

Xəritələrin ç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.

Şəklin 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 edin 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-ci nümunədə 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.