eolymp
bolt
Try our new interface for solving problems
Məsələlər

Выпуклая оболочка

Выпуклая оболочка

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Поиск выпуклой оболочки множества точек является важной задачей, которая часто является частью более широкой задачи. Есть много алгоритмов для нахождения выпуклой оболочки. Так как задачи, связанные с выпуклой оболочкой, иногда появляются в ACM - чемпионатах мира по программированию, то это хорошая идея для участников узнать более подробно некоторые из этих алгоритмов.

Нахождение выпуклой оболочки множества точек на плоскости может быть разделено на две подзадачи. Во-первых, дано множество точек. Нужно найти подмножество тех точек, которые вместе с отрезками, их соединяющими, имеют форму выпуклого многоугольника, который охватывает все исходные точки. Во-вторых, вывести все точки выпуклой оболочки, идя против часовой стрелки вокруг многоугольника. В этой задаче, задача первой подкатегории уже сделана за вас, а ваша программа должна решать вторую подзадачу. То есть, учитывая те точки, которые, как известно, лежат на выпуклой оболочке, вывести их в порядке обхода против часовой стрелки вокруг многоугольника.

Giriş verilənləri

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

Çıxış verilənləri

В первую строку в выходном файле выведите одно целое число m – число точек на выпуклой оболочке. В последующих m строчках выведите по паре чисел, каждая из которых описывает точку на выпуклой оболочки, в порядке обхода против часовой стрелки вокруг многоугольника. Каждая из этих строк должна содержать x-координату точки, затем пробел, а затем y-координату точки. Начните с точки на многоугольнике, у которой координата x минимальна. Если есть несколько таких точек, начните с той, чья координата y минимальна.

Nümunə

Giriş verilənləri #1
5
1 1 Y
1 -1 Y
0 0 N
-1 -1 Y
-1 1 Y
Çıxış verilənləri #1
4
-1 -1
1 -1
1 1
-1 1