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

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

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

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Дано n точек на плоскости. Построить их выпуклую оболочку. Гарантируется, что выпуклая оболочка не вырождена.

Входные данные

В первой строке задано количество точек n (3n10^5). Следующие n строк содержат пары целых чисел x[i] и y[i] (-10^9x[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