Qabarıq qabıq#2294
Nöqtələrin çoxluğunun konveks örtüyünü (konveks qabığını) tapmaq mühüm bir problemdir və tez-tez daha böyük bir problemin tərkib hissəsi olur. Konveks örtüyü tapmaq üçün bir çox alqoritm mövcuddur. Konveks örtük ilə bağlı məsələlər bəzən ACM proqramlaşdırma dünya çempionatlarında rast gəlinir, buna görə iştirakçıların bu alqoritmlərin bəzilərini bilməsi yaxşı olar.
Müstəvidə nöqtələrin çoxluğunun konveks örtüyünü tapmaq problemini iki alt-altapşırığa bölmək olar. Birinci, nöqtələrin çoxluğundan, bu nöqtələri birləşdirən düz xətlər konveks çoxbucaqlı əmələ gətirəcək və bütün həqiqi (əsas) nöqtələri içinə alacaq alt çoxluğunu tapmaq lazımdır. İkinci isə, konveks örtüyün nöqtələrini konveks çoxbucaqlının ətrafında saat əqrəbinin əksi istiqamətində gedərək düzüliş sırasına uyğun çap etmək lazımdır. Bu məsələdə birinci alt-altapşırıq artıq sizin yerinizə yerinə yetirilib və proqramınız yalnız ikinci alt-altapşırığı həll etməlidir. Beləliklə, konveks örtükdə olduqları məlum olan nöqtələr verilir və siz onları konveks örtük üzərində saat əqrəbinin əksi istiqamətində düzüımək üzrə sıralamalısınız.
Girişin ilk sətrində 3 \le n \le 100000 bütöv ədədi, nöqtələrin sayı verilir. Növbəti sətrdə hər biri bir nöqtəni təsvir edən məlumatlar verilir. Hər sətrdə iki tam ədəd və sonda bir Y və ya bir N verilib, onlar boşluq ilə ayrılıb. İki tam ədəd nöqtənin və koordinatlarını bildirir. Y simvolu həmin nöqtənin bütün nöqtələrin konveks örtüyünün üzərində yerləşdiyini, N isə yerləşmədiyini göstərir. Nöqtələrin və koordinatları heç vaxt -dan kiçik, -dan böyük olmayacaq. Girişdə heç bir nöqtə iki dəfə təkrar olunmayacaq. Girişdəki nöqtələrin heç biri bir düz xətt üzərində yerləşməyəcək.
Əvvəlcə, bir sətirdə konveks örtükdə yerləşən nöqtələrin sayı çıxarılmalıdır. Növbəti sətrdə isə hər bir konveks örtükdə olan nöqtə, çoxbucaqlının ətrafında saat əqrəbinin əksi istiqamətində düzüliş sırasına uyğun olaraq yazılmalıdır. Hər sətirdə nöqtənin əvvəlcə koordinatı, sonra boşluq və sonra koordinatı verilməlidir. Başlamaq üçün ən kiçik koordinatına sahib olan konveks örtükdəki nöqtədən başlayın. Əgər belı bir neçə nöqtə varsa, onların arasında koordinatı ən kiçik olanından başlayın.
Nümunə 1