Neqabarıq çoxbucaqlılarının kəsişməsi#4389
Əksər rəsmlər və təsvirətmə proqramlarında poliqon obyektləri yaratmaq üçün sadə alətlər mövcuddur. Daha yaxşı proqramlar iki poliqonun kəsişmə sahələrini də tapa bilir. Aşağıdakı şəkildə birisi beşbucaqlı, digəri isə üçbucaqlı olan iki poliqon göstərilmişdir. Onların kəsişməsi iki tünd sahədən ibarətdir.
IBM sizi proqramlaşdırma komandası üzvü kimi yeni işə qəbul edib və sizdən yüksək səviyyəli rəsmlər/təsvirətmə proqramı üçün kod yazmaq tələb olunur. Sizin tapşırığınız, proqramın poliqonların kəsişməsi ilə bağlı olan hissəsini yazmaqdır. Rəhbəriniz sizə istifadəçi interfeysi üzərində işləməyi hələ ki, təxirə salmağı və yalnız kəsişmə bölgələrinin həndəsi təsvirlərinə fokuslanmağı tapşırıb.
Kartes koordinat müstəvisində bir poliqon onun zirvələrinin ardıcıllığı ilə təsvir oluna bilər. Bu ardıcıllıqda zirvələr poliqonun sərhədi ilə saat əqrəbi istiqamətində hərəkət edərkən ardıcıl ziyarət olunur; beləliklə, ardıcıl iki zirvə poliqonun bir tərəfini təşkil edən xətt parçasının uclarıdır. Ardıcıll ardıcıllıqda sonuncu və birinci zirvə də bir tərəfin uclarıdır. Zirvələr onların və koordinatları ilə müəyyən edilir. Hər bir poliqon üçün aşağıdakıları fərz edin:
Eyni poliqonda heç bir nöqtə zirvə kimi bir dəfədən artıq təkrarlanmır.
İki tərəf yalnız ümumi ucdə (zirvədə) kəsişə bilər.
Ümumi ucdə birləşən iki tərəf arasındakı bucaq -dan böyük və dərəcədən kiçikdir.
PoliQonun ən azı zirvəsi var.
İki poliqonun kəsişməsi və ya daha çox birləşik bölgədən ibarət ola bilər. Sizin tapşırığınız iki poliqonu qəbul etmək və onların kəsişmə sahələrini, yəni yuxarıdakı kriteriyalara cavab verən poliqonları müəyyən etməkdir.
Daxil olan məlumatda hər biri iki poliqondan ibarət olan bir neçə məlumat dəsti var. Hər bir poliqon aşağıdakı ardıcıllıqla verilir:
\mathbf{n},\ x_1,\ y_1,\ x_2,\ y_2,\ \ldots,\ x_n,\ y_n
burada tam ədəd — poliqonun zirvələrinin sayıdır, və həqiqi koordinatlar (x_1, y_1)-dən (x_n, y_n)-dək sərhəd zirvələridir. Daxil olan məlumatın sonu üçün iki sıfırla işarə olunur. Bu iki sıfır yalnız məlumatların sonunu göstərir, əlavə məlumat dəsti kimi qəbul edilməməlidir.
Hər məlumat dəsti üçün, proqramınız onun nömrəsini (**Data set 1**, **Data set 2**, və s.), və iki poliqonun kəsişmə bölgələrinin sayını çıxmalıdır. Hər bölgənin etiketini (**Region 1**, **Region 2**, və s.) göstərin və zirvələrini ya saat əqrəbi istiqamətində, ya da onun əksi istiqamətində sərhəd boyunca ziyarət olunduqları ardıcıllıqla sadalayın. Birinci çap olunan zirvə ən kiçik -koordinatına sahib olan olmalıdır (bərabərlik olduqda ən kiçik -koordinatlı seçilir). Heç bir bölgəyə deqenerasiya olunmuş hissələr (yani kəsişmə bucağı olan ardıcıl tərəflər) daxil edilməməlidir. Əgər ardıcıl iki tərəfin üç ucu bir düz xətt üzərindədirsə, bu iki tərəf bir tərəfə birləşdirilməlidir. Hər zirvəni standart formada yazın; burada və vergüldən sonra iki rəqəm olmaqla çıxarılır. Aşağıda verilən nümunə giriş yalnız bir məlumat dəsti (və bu sual təsvirinin başında yerləşən şəkilə uyğun) ehtiva edir.
Nümunə 1