Выпуклая оболочка - точки
На плоскости даны $N$ точек. Вам требуется построить выпуклую оболочку данного множества точек. Если $N$ нечетно, то оболочку нужно выводить в порядке обхода по часовой стрелке, иначе — против часовой стрелки.
Входные данные
Первая строка содержит количество точек $N$, $1\le N\le 20\,000$. Каждая из последующих $N$ строк содержит два целых числа — координаты $x_i$ и $y_i$. Все числа по модулю не превосходят $10^4$.
Выходные данные
Выходной файл должен иметь тот же формат, что и входной, и должен содержать выпуклую оболочку. Количество точек в выходном файле должно быть минимально возможным.
Примеры
Входные данные
4 0 0 3 4 3 1 6 0
Выходные данные
3 6 0 3 4 0 0
algoprog.ru © Петр Калинин, GNU AGPL, github.com/petr-kalinin/algoprog | О лицензии на материалы сайта | Блог