Qril nöqtələrinin konveks qabığı
Şəbəkə nöqtəsi tam ədədi koordinatlara malik olan nöqtəyə deyilir. Şəbəkə çoxbucağı isə təpələri yalnız şəbəkə nöqtələrindən ibarət olan çoxbucaqdır.
Bir çoxbucaq qabarıq adlanır, əgər onun istənilən iki nöqtəsini birləşdirən parça tamamilə çoxbucağın daxilində (və ya sərhədində) yerləşirsə. Başqa sözlə, əgər çoxbucağın hər bir daxili bucağı 180 dərəcədən kiçikdirsə, o qabarıqdır.
S şəbəkə nöqtələrinin qabarıq zərfi bu nöqtə çoxluğunu əhatə edən ən kiçik qabarıq çoxbucaqdır (şəbəkə çoxbucağı). (Qabarıq zərfin təpələri şəbəkə nöqtələri çoxluğuna S aid olmalıdır). Əgər bütün nöqtələr bir düz xətt üzərində yerləşirsə, onların qabarıq zərfi bir parça olacaq (degenerasiya olunmuş çoxbucaq - ən sağdakı şəkildə göstərildiyi kimi). Aşağıdakı şəkillərdə nöqtə çoxluqları qalın nöqtələrlə işarələnib, qabarıq zərfin təpələri X ilə göstərilib və qabarıq zərf təpələri birləşdirən parçalar şəklində təsvir edilib. Qabarıq zərfin bütün nöqtələri onun təpələri deyil.
Şəbəkə çoxbucağının təpələri standart qaydada yerləşir, əgər:
a) Birinci təpə ən böyük y koordinatına malikdir. Əgər iki təpə eyni y koordinatına malikdirsə, birinci x kiçik olan təpə sayılır.
b) Çoxbucağın təpələri saat əqrəbi istiqamətində verilir.
Şəbəkə nöqtələri çoxluğunu oxuyan və qabarıq zərfin təpələrini standart qaydada çıxaran bir proqram yazın.
Giriş verilənləri
Birinci sətir yeganə tam ədəd P (1 ≤ P ≤ 1000) - testlərin sayını ehtiva edir. Hər testin birinci sətri onun nömrəsini, boşluq və çoxluqdakı nöqtələrin sayını N (3 ≤ N ≤ 50) ehtiva edir. Sonra çoxluq nöqtələri verilir, hər sətirdə ən çox 5 nöqtə (sonuncu sətirdə daha az ola bilər). Hər nöqtə boşluqla ayrılmış iki tam ədəd ilə verilir, bu ədədlər onun x və y koordinatlarını təsvir edir.
Çıxış verilənləri
Hər test üçün bir neçə sətir çıxarılmalıdır. Birinci sətir testin nömrəsini və qabarıq zərfin təpələrinin sayını ehtiva edir. Sonra qabarıq zərfin təpələri standart qaydada, hər sətirdə bir təpə olmaqla verilir. Hər sətir təpənin x və y koordinatını, boşluqla ayrılmış şəkildə ehtiva edir.