EduBrick

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

1000 мс · 256 МБ · всё или ничего

Дан набор точек. Постройте его выпуклую оболочку - наименьший выпуклый многоугольник, содержащий все точки.

Формат ввода

В первой строке - число точек nn (1≤n≤1051 \le n \le 10^5).

В следующих nn строках - координаты точек, целые, по модулю не превосходящие 10610^6. Точки могут повторяться.

Формат вывода

В первой строке выведите число вершин оболочки, затем сами вершины.

Начинайте с самой левой из самых нижних точек и идите против часовой стрелки. Точки, лежащие внутри сторон, выводить не нужно.

Примеры

ввод
5
0 0
2 0
2 2
0 2
1 1
вывод
4
0 0
2 0
2 2
0 2
ввод
3
0 0
1 1
2 2
вывод
2
0 0
2 2
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.