Опукла оболонка#2294
Знаходження опуклої оболонки множини точок — важлива задача, яка часто є частиною більшої задачі. Існує багато алгоритмів знаходження опуклої оболонки. Оскільки задачі, пов’язані з опуклою оболонкою, іноді з’являються на чемпіонатах світу з програмування ACM, корисно знати деякі з цих алгоритмів.
Задачу знаходження опуклої оболонки для множини точок на площині можна поділити на дві підзадачі. Перше: задано набір точок, знайти підмножину цих точок, які, якщо їх з’єднати відрізками, утворюють опуклий багатокутник, що охоплює всі початкові точки. Друге: вивести точки опуклої оболонки у певному порядку, "обходячи" багатокутник проти годинникової стрілки. У цій задачі перше підзавдання вже виконано за вас, і ваша програма повинна виконати друге підзавдання. Тобто, задані точки, про які відомо, що вони лежать на опуклій оболонці, вивести їх у порядку проти годинникової стрілки по оболонці.
У першому рядку вхідних даних задано одне ціле число 3 \le n \le 100000 — кількість точок. Наступні рядків описують точки. У кожному з цих рядків міститься два цілих числа та або літера Y, або N, розділені пробілами. Два цілих числа задають - і -координати точки. Символ Y означає, що точка лежить на опуклій оболонці всіх точок, а N — що не лежить. - і -координати кожної точки не менші і не більші . Жодна точка не зустрічається у вхідних даних більше одного разу. Точки у вхідних даних ніколи не лежать усі на одній прямій.
Спочатку виведіть єдиний рядок із числом — кількістю точок на опуклій оболонці. Далі виведіть рядків, кожен описує одну точку опуклої оболонки у порядку проти годинникової стрілки по оболонці. Кожен з цих рядків повинен містити -координату точки, пробіл, -координату точки. Починайте з тієї точки оболонки, у якої -координата мінімальна. Якщо таких кілька, починайте з тієї з них, у якої -координата мінімальна.
Приклад 1