Задано n точок на площині. Побудувати їх опуклу оболонку. Гарантується, що опукла оболонка не вироджена.
У першому рядку задана кількість точок n (3 ≤ n ≤ 10^5
). Наступні n рядків містять пари цілих чисел x[i]
та y[i]
(-10^9
≤ x[i]
, y[i]
≤ 10^9
) - координати точок.
Будьте акуратними! Точки довільні. Бувають співпадаючі, бувають такі, що лежать на одній прямій і у великій кількості.
У першому рядку виведіть число вершин n опуклої оболонки. Наступні n рядків повинні містити координати вершин у порядку обходу. Ніякі три точки, що йдуть підряд, не повинні лежати на одній прямій.