Задачи
Выпуклая оболочка
Выпуклая оболочка
Дано n точек на плоскости. Построить их выпуклую оболочку. Гарантируется, что выпуклая оболочка не вырождена.
Входные данные
В первой строке задано количество точек n (3 ≤ n ≤ 10^5
). Следующие n строк содержат пары целых чисел x[i]
и y[i]
(-10^9
≤ x[i]
, y[i]
≤ 10^9
) - координаты точек.
Будьте аккуратны! Точки произвольны. Бывают совпадающие, бывают лежащие на одной прямой в большом количестве.
Выходные данные
В первой строке выведите количество вершин n выпуклой оболочки. Следующие n строк должны содержать координаты вершин в порядке обхода. Никакие три подряд идущие точки не должны лежать на одной прямой.
Пример
Входные данные #1
5 0 0 2 0 0 2 1 1 2 2
Выходные данные #1
4 0 0 0 2 2 2 2 0