Daxili nöqtələr şəbəkəli çoxbucaqlının
Daxili nöqtələr tam ədədi koordinatlara malik nöqtələrdir. Şəbəkə çoxbucağı isə tam ədədi koordinatlara malik nöqtələrdə zirvələri olan çoxbucaqdır.
Çoxbucağın sərhədində yerləşən tam ədədi koordinatlara malik nöqtələr sərhəd nöqtələri adlanır (yuxarıdakı şəkildə rənglənməmiş nöqtələr kimi göstərilmişdir), daxili nöqtələr isə çoxbucağın içərisində yerləşən və tam ədədi koordinatlara malik nöqtələrdir (yuxarıdakı şəkildə rənglənmiş nöqtələr kimi göstərilmişdir).
Çoxbucaq, hər hansı bir parçası ya sərhədində, ya da içərisində yerləşirsə, qabarıq adlanır. Bu, çoxbucağın hər hansı bir daxili bucağının 180 dərəcədən kiçik olması ilə eynidir. Qeyd edək ki, iki daxili nöqtə arasındakı hər hansı bir parça həmişə çoxbucağın içərisində yerləşir, lakin sərhədində deyil.
Qabarıq şəbəkə çoxbucağının daxili nöqtələri hər hansı üfüqi xətt üzərində sol ən uc nöqtədən sağ ən uc nöqtəyə qədər (üst-üstə düşə bilər) tək bir seqment təşkil edir. Qeyd edək ki, heç bir daxili nöqtə olmaya bilər (A), yalnız bir daxili nöqtə ola bilər (B) və ya təcrid olunmuş daxili nöqtələr ola bilər (C), aşağıdakı şəkillərdə göstərildiyi kimi.
Qabarıq şəbəkə çoxbucağının zirvələrini standart qaydada oxuyan və onun daxili nöqtələrinin siyahısını üfüqi seqmentlər şəklində çıxaran bir proqram yazın. Şəbəkə çoxbucağının zirvələri standart qaydada yerləşdirilibsə:
a) İlk zirvə ən böyük y koordinatına malikdir. İki zirvə eyni y dəyərinə malikdirsə, daha kiçik x koordinatına malik zirvə birinci göstərilir.
b) Zirvələr çoxbucağın ətrafında saat əqrəbi istiqamətində verilir.
Giriş verilənləri
Giriş faylının ilk sətiri P (1 ≤ P ≤ 1000) tam ədədini ehtiva edir, bu, növbəti test məlumat dəstlərinin sayını göstərir. Hər bir məlumat dəstinin ilk sətiri test nümunəsinin nömrəsini və sonra boşluqla ayrılmış çoxbucağın zirvələrinin sayını N (3 ≤ N ≤ 50) ehtiva edir. Hər bir məlumat dəstindəki digər sətirlər zirvələri standart qaydada, hər sətirdə bir zirvə olmaqla ehtiva edir. Hər sətir əvvəlcə x koordinatını, sonra isə y koordinatını ehtiva edir. Bütün koordinatlar tam ədədlərdir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün bir neçə sətir çıxarın. İlk sətirdə onluq tam ədəd - test məlumat dəstinin nömrəsini və sonra boşluqla ayrılmış onluq tam ədəd - daxili nöqtələri ehtiva edən üfüqi sətirlərin sayını (bu, sıfır (0) və ya daha çox ola bilər) çıxarın. Daxili nöqtələrin sətirləri varsa, onlar y dəyərinin azalan qaydasında hər sətirdə bir sətir olmaqla verilir. Hər sətir əvvəlcə onluq tam ədəd - nöqtələrin sətirinin y- koordinatını və sonra boşluqla ayrılmış şəkildə həmin sətirdəki ən sol nöqtənin x- koordinatını və həmin sətirdəki ən sağ nöqtənin x- koordinatını ehtiva edir.