Опукла оболонка
Пошук опуклої оболонки множини точок є важливою задачею, яка часто є частиною більше загальної задачі. Є багато алгоритмів для знаходження опуклої оболонки. Так як задачі, пов'язані з опуклою оболонкою, іноді з'являються в ACM - чемпіонатах світу з програмування, то це гарна ідея для учасників познайомитись більш детально з деякими з цих алгоритмів.
Знаходження опуклої оболонки множини точок на площині може бути розділено на дві підзадачи. По-перше, задано множину точок. Портібно знайти підмножину таких точок, які разом з відрізками, що їх з'єднують, мають форму опуклого многокутника, який охоплює усі задані точки. По-друге, вивести усі точки опуклої оболонки, йдучи проти годинникової стрілки навколо многокутника. У цій задачі, задача першої підкатегорії вже зроблена за вас, а ваша програма повинна розв'язувати другу підзадачу. Тобто, враховуючи ті точки, які, як відомо, лежать на опуклій оболонці, вивести їх у порядку обходу проти годинникової стрілки навколо многокутника.
Вхідні дані
Перший рядок вхідного файлу містить одне ціле число 3 ≤ N ≤ 100000, кількість точок. Наступні рядки вхідного файлу задають кожну точку. Кожен з цих рядків містить два цілих числа і або Y, або N, відокремлені пропусками. Два цілих числа визначають x- та y-координати точки. Y вказує, що точка знаходиться на опуклій оболнці усіх точок, а N вказує, що це не так. x- та y-координати кожної точки будуть не менші, ніж -1000000000 і не більше 1000000000. Кожну точку задано лише один раз. Точки у вхідних даних ніколи не лежать на одній прямій.
Вихідні дані
У перший рядок у вихідному файлі виведіть одно ціле число m – кількість точек на опуклій оболонці. У наступних m рядках виведіть по парі чисел, кожне з яких описує точку на опуклій оболнці, у порядку обходу проти годинникової стрілки навколо многокутника. Кожен з цих рядків повинен містити x-координату точки, потім пропуск, а далі y-координату точки. Почніть з точки на многокутнику, у якого координата x мінімальна. Якщо є декілька таких точок, почніть з тієї, чия координата y мінімальна.