Qabarıq qabıq
Nöqtələr çoxluğunun konveks qabığını tapmaq mühüm bir məsələdir və tez-tez daha geniş problemlərin bir hissəsi kimi qarşıya çıxır. Konveks qabığın tapılması üçün bir çox alqoritm mövcuddur. Bu mövzu, ACM proqramlaşdırma üzrə dünya çempionatlarında da rast gəlinə biləcəyi üçün iştirakçıların bu alqoritmlərlə yaxından tanış olması faydalıdır.
Müəyyən bir müstəvidə nöqtələr çoxluğunun konveks qabığını tapmaq iki alt məsələyə bölünə bilər. Birincisi, nöqtələr çoxluğu verilir və bu nöqtələri birləşdirən seqmentlərlə birlikdə bütün verilmiş nöqtələri əhatə edən konveks çoxbucaqlı formasında olan nöqtələrin alt çoxluğunu tapmaq lazımdır. İkincisi, çoxbucağın ətrafında saat əqrəbi istiqamətinin əksinə gedərək konveks qabığın bütün nöqtələrini çıxarmaq lazımdır. Bu məsələdə, birinci alt məsələ artıq sizin üçün həll edilib və sizin proqramınız ikinci alt məsələnin həllini tapmalıdır. Yəni, konveks qabıqda olduğu məlum olan nöqtələri çoxbucağın ətrafında saat əqrəbi istiqamətinin əksinə gedərək çıxarmaq lazımdır.
Giriş verilənləri
Giriş faylının ilk sətiri bir tam ədəd 3 ≤ N ≤ 100000, nöqtələrin sayını ehtiva edir. Giriş faylının növbəti sətirləri hər bir nöqtəni təyin edir. Bu sətirlərin hər biri iki tam ədəd və ya Y, ya da N ehtiva edir, boşluqlarla ayrılmışdır. İki tam ədəd nöqtənin x- və y-koordinatlarını təyin edir. Y nöqtənin bütün nöqtələrin konveks qabığında olduğunu göstərir, N isə bunun belə olmadığını göstərir. Hər bir nöqtənin x- və y-koordinatları -1000000000-dən az və 1000000000-dən çox olmayacaq. Hər bir nöqtə yalnız bir dəfə verilir. Girişdəki nöqtələr heç vaxt bir xətt üzərində yerləşmir.
Çıxış verilənləri
Çıxış faylının ilk sətirində bir tam ədəd m – konveks qabıqda olan nöqtələrin sayını çıxarın. Növbəti m sətirdə konveks qabıqda olan nöqtəni təsvir edən hər bir cüt ədədi çıxarın, çoxbucağın ətrafında saat əqrəbi istiqamətinin əksinə gedərək. Bu sətirlərin hər biri nöqtənin x-koordinatını, sonra boşluq, daha sonra nöqtənin y-koordinatını ehtiva etməlidir. Ən kiçik x koordinatına malik nöqtədən başlayın. Əgər bir neçə belə nöqtə varsa, ən kiçik y koordinatına malik olan nöqtədən başlayın.