Задача №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
Сдать: для сдачи задач необходимо войти в систему