H. Выпуклая оболочка
1000 мс · 256 МБ · всё или ничего
Дан набор точек. Постройте его выпуклую оболочку - наименьший выпуклый многоугольник, содержащий все точки.
Формат ввода
В первой строке - число точек ().
В следующих строках - координаты точек, целые, по модулю не превосходящие . Точки могут повторяться.
Формат вывода
В первой строке выведите число вершин оболочки, затем сами вершины.
Начинайте с самой левой из самых нижних точек и идите против часовой стрелки. Точки, лежащие внутри сторон, выводить не нужно.
Примеры
ввод
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
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.