eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Опукла оболонка

Опукла оболонка

\includegraphics{https://static.e-olymp.com/content/79/7913cb36340b423d9e084d35c5564c08ba525c23.jpg} Пошук опуклої оболонки множини точок є важливою задачею, яка часто є частиною більше загальної задачі. Є багато алгоритмів для знаходження опуклої оболонки. Так як задачі, пов'язані з опуклою оболонкою, іноді з'являються в ACM - чемпіонатах світу з програмування, то це гарна ідея для учасників познайомитись більш детально з деякими з цих алгоритмів. Знаходження опуклої оболонки множини точок на площині може бути розділено на дві підзадачи. По-перше, задано множину точок. Портібно знайти підмножину таких точок, які разом з відрізками, що їх з'єднують, мають форму опуклого многокутника, який охоплює усі задані точки. По-друге, вивести усі точки опуклої оболонки, йдучи проти годинникової стрілки навколо многокутника. У цій задачі, задача першої підкатегорії вже зроблена за вас, а ваша програма повинна розв'язувати другу підзадачу. Тобто, враховуючи ті точки, які, як відомо, лежать на опуклій оболонці, вивести їх у порядку обходу проти годинникової стрілки навколо многокутника. \InputFile Перший рядок вхідного файлу містить одне ціле число \textbf{3} ≤ \textbf{N} ≤ \textbf{100000}, кількість точок. Наступні рядки вхідного файлу задають кожну точку. Кожен з цих рядків містить два цілих числа і або \textbf{Y}, або \textbf{N}, відокремлені пропусками. Два цілих числа визначають \textbf{x}- та \textbf{y}-координати точки. \textbf{Y} вказує, що точка знаходиться на опуклій оболнці усіх точок, а \textbf{N} вказує, що це не так. \textbf{x}- та \textbf{y}-координати кожної точки будуть не менші, ніж \textbf{-1000000000} і не більше \textbf{1000000000}. Кожну точку задано лише один раз. Точки у вхідних даних ніколи не лежать на одній прямій. \OutputFile У перший рядок у вихідному файлі виведіть одно ціле число \textbf{m} -- кількість точек на опуклій оболонці. У наступних \textbf{m} рядках виведіть по парі чисел, кожне з яких описує точку на опуклій оболнці, у порядку обходу проти годинникової стрілки навколо многокутника. Кожен з цих рядків повинен містити \textbf{x}-координату точки, потім пропуск, а далі \textbf{y}-координату точки. Почніть з точки на многокутнику, у якого координата \textbf{x} мінімальна. Якщо є декілька таких точок, почніть з тієї, чия координата \textbf{y} мінімальна.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
5
1 1 Y
1 -1 Y
0 0 N
-1 -1 Y
-1 1 Y
Вихідні дані #1
4
-1 -1
1 -1
1 1
-1 1