Выпуклая оболочка
Поиск выпуклой оболочки множества точек является важной задачей, которая часто является частью более широкой задачи. Есть много алгоритмов для нахождения выпуклой оболочки. Так как задачи, связанные с выпуклой оболочкой, иногда появляются в ACM - чемпионатах мира по программированию, то это хорошая идея для участников узнать более подробно некоторые из этих алгоритмов.
Нахождение выпуклой оболочки множества точек на плоскости может быть разделено на две подзадачи. Во-первых, дано множество точек. Нужно найти подмножество тех точек, которые вместе с отрезками, их соединяющими, имеют форму выпуклого многоугольника, который охватывает все исходные точки. Во-вторых, вывести все точки выпуклой оболочки, идя против часовой стрелки вокруг многоугольника. В этой задаче, задача первой подкатегории уже сделана за вас, а ваша программа должна решать вторую подзадачу. То есть, учитывая те точки, которые, как известно, лежат на выпуклой оболочке, вывести их в порядке обхода против часовой стрелки вокруг многоугольника.
Входные данные
Первая строка входного файла содержит одно целое число 3 ≤ N ≤ 100000, количество точек. Следующие строки входного файла задают каждую точку. Каждая из этих строк содержит два целых числа и либо Y, либо N, разделенные пробелами. Два целых чисел определяют x- и y-координаты точки. Y указывает, что точка находится на выпуклой оболочке всех точек, а N указывает, что это не так. x- и y-координаты каждой точки будут не меньше, чем -1000000000 и не более 1000000000. Каждая точка задана только один раз. Точки во входных данных никогда не лежат на одной прямой.
Выходные данные
В первую строку в выходном файле выведите одно целое число m – число точек на выпуклой оболочке. В последующих m строчках выведите по паре чисел, каждая из которых описывает точку на выпуклой оболочки, в порядке обхода против часовой стрелки вокруг многоугольника. Каждая из этих строк должна содержать x-координату точки, затем пробел, а затем y-координату точки. Начните с точки на многоугольнике, у которой координата x минимальна. Если есть несколько таких точек, начните с той, чья координата y минимальна.