Задача №1877. Выпуклая оболочка
На плоскости даны \(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
Сдать: для сдачи задач необходимо войти в систему