Daxili nöqtələr şəbəkəli çoxbucaqlının#2447
Qəfəs nöqtəsi tam ədədi koordinatlara malik nöqtəyə deyilir. Qəfəs çoxbucaqlısı isə bütün təpələri qəfəs nöqtəsi olan çoxbucaqlıdır.
Çoxbucaqlının sərhədində yerləşən qəfəs nöqtələri sərhəd nöqtələridir (yuxarıdakı şəkildə açıq dairələr), çoxbucaqlının daxilində olan və sərhədində olmayan nöqtələr isə daxili nöqtələrdir (yuxarıdakı şəkildə dolu dairələr).
Çoxbucaqlı o vaxt konveks adlanır ki, çoxbucaqlının istənilən iki nöqtəsini birləşdirən xətt parçası tamamilə çoxbucaqlının içində (və ya sərhədində) yerləşsin. Başqa sözlə, hər bir təpədəki daxili bucaq dərəcədən kiçik olmalıdır. Qeyd edək ki, çoxbucaqlının içində (və sərhədində olmayan) iki nöqtəni birləşdirən hər bir xətt parçası bütövlüklə çoxbucaqlının içində və sərhədində olmayacaqdır.
Yatay xətt üzrə konveks qəfəs çoxbucaqlısının daxili nöqtələri sola ən yaxın nöqtədən sağa ən yaxın nöqtəyədək olan bir hissəni təşkil edir (bu iki nöqtə bir-birinə bərabər də ola bilər). Qeyd: heç bir daxili nöqtə olmaya bilər (A), yalnız bir dənə ola bilər (B), yaxud ayrı-ayrı daxili nöqtələr ola bilər (C) — bunlar aşağıdakı şəkildə göstərilmişdir.
Proqram yazın ki, konveks qəfəs çoxbucaqlısının təpələrini standart düzülüşdə oxuyub, onun daxili nöqtələrini üfüqi xətlər üzrə istiqamətlərlə verilsin. Qəfəs çoxbucaqlısının təpələri aşağıdakı standart qaydada verilir:
[(a)] Birinci təpə ən böyük qiymətinə malik təpədir. Əgər iki təpənin -si bərabərdirsə, -i ən kiçik olan birinci gəlir.
[(b)] Təpələr çoxbucaqlının ətrafında saat əqrəbi istiqamətində sıralanır.
Girişin ilk sətrində (1 \leq P \leq 1000) — verilən məlumatlar dəstinin sayı verilir. Hər bir məlumat dəstəsinin ilk sətrində dəstə nömrəsi, bir boşluq, sonra isə çoxbucaqlının təpələrinin sayı (3 \leq N \leq 50) verilir. Sonrakı sətrlərdə təpə standart düzülüşdə bir-bir verilir. Hər sətirdə tam ədəd olan koordinatı, bir boşluq və tam ədəd olan koordinatı verilir. Bütün koordinatlar tam ədəddir.
Hər dəstəyə görə bir neçə sətir çap edin. Birinci sətrdə dəstə nömrəsi, bir boşluq və daxili nöqtə olan horizontal (üfüqi) xətlərin sayı olmaqla (bu, və ya daha çox ola bilər). Əgər daxili nöqtələr varsa, onlar növbəti sətrlərdə -nin azalan ardıcıllığında verilir. Hər satırda koordinatı, həmin xətt üzrə ən soldakı daxili nöqtənin koordinatı və ən sağdakı daxili nöqtənin koordinatı ardıcıllıqla aralarında boşluq olmaqla verilir.
Nümunə 1