Neqabarıq çoxbucaqlılarının kəsişməsi
Əksər rəsm və ya illüstrasiya proqramları çoxbucaqlılar yaratmaq üçün sadə vasitələrə malikdir. Ən yaxşıları isə iki çoxbucaqlının kəsişmə sahəsini tapa bilir. Aşağıdakı şəkildə iki çoxbucaq təsvir edilmişdir: biri beşbucaq, digəri isə üçbucaqdır. Onların kəsişmə sahəsi iki qaranlıq sahədən ibarətdir.
IBM sizi yeni bir rəsm/illüstrasiya proqramı hazırlamaq üçün proqramçılar qrupunun üzvü kimi işə götürdü. Sizin vəzifəniz çoxbucaqlıların kəsişmələri ilə işləyən bir proqram hazırlamaqdır. Rəhbəriniz sizdən istifadəçi interfeysindən uzaqlaşıb kəsişmələrin həndəsi təmsilinə diqqət yetirməyinizi xahiş etdi.
Dekart koordinat sistemində çoxbucaq onun zirvələrinin ardıcıllığı ilə təqdim olunur. Zirvələr ardıcıllıqla çoxbucağın sərhədini saat əqrəbi istiqamətində keçmə qaydasında verilir; beləliklə, istənilən iki qonşu zirvə çoxbucağın tərəfi olan bir xətt parçasının uclarıdır. Ardıcıllığın sonuncu və birinci nöqtələri də çoxbucağın tərəfinin uclarıdır. Zirvələr öz x və y koordinatları ilə verilir. Aşağıdakı ifadələr hər bir çoxbucaq üçün doğrudur:
Heç bir nöqtə (bir çoxbucaqda) bir dəfədən çox zirvə deyil.
İki tərəf yalnız ümumi bir nöqtədə (zirvədə) kəsişə bilər.
Ümumi zirvəsi olan istənilən iki tərəf arasındakı bucaq həmişə 0-dan böyük və 360 dərəcədən kiçikdir.
Çoxbucaq ən azı 3 zirvəyə malikdir.
İki çoxbucağın kəsişməsi 0 və ya daha çox əlaqəli sahədən ibarətdir. İki çoxbucaq verildikdə, onların kəsişmə sahələrini müəyyənləşdirmək lazımdır.
Giriş verilənləri
Giriş məlumatları bir neçə testdən ibarətdir, hər biri iki çoxbucaqdan ibarətdir. Hər bir çoxbucaq nömrələr ardıcıllığı ilə verilir:
n, x_1, y_1, x_2, y_2, ..., x_n, y_n
burada n - zirvələrin sayı, (x_1, y_1)-dən (x_n, y_n)-ə qədər olan həqiqi ədədlər sərhəd zirvələrinin koordinatlarını təmsil edir. Giriş məlumatlarının sonunda iki sıfır n dəyəri kimi verilir. Onlar məlumatların sonunu göstərir və ayrıca test kimi qəbul edilməməlidir.
Çıxış verilənləri
Hər bir test üçün onun nömrəsini (Data set 1, Data set 2 və s.) və iki çoxbucağın kəsişmə sahələrinin sayını çıxarın. Testdə hər bir sahəni (Region 1, Region 2 və s.) nömrələyin və onun zirvələrini sahənin sərhədini saat əqrəbi istiqamətində və ya əksinə keçmə qaydasında çıxarın. Ən kiçik x koordinatına malik zirvəni birinci çıxarın (əgər belə bir neçə varsa, ən kiçik y koordinatına malik olanı). Heç bir sahə özündə degenerasiya olunmuş sahələri (aralarındakı bucaq 0 olan qonşu tərəfləri) daxil etməməlidir. Əgər iki qonşu tərəfin üç nöqtəsi kolineardırsa, bu tərəflər birləşdirilməlidir. Hər bir zirvəni (x, y) formatında çıxarın, burada x və y iki onluq rəqəmi ehtiva edir. Aşağıdakı nümunə bir testi ehtiva edir (bu, məsələnin şəklinə uyğundur).