There are n points on the plane. Build their convex hull. It is guaranteed that the convex hull is non-degenerate.
The first line contains the number of points n (3 ≤ n ≤ 10^5
). Each of the next n lines contains pair of integers x[i]
and y[i]
(-10^9
≤ x[i]
, y[i]
≤ 10^9
) - the points coordinates.
Be careful! The points are random. The points can be identical, can lie on a straight line, and there is a lot of them.
В первой строке выведите количество вершин n выпуклой оболочки. Следующие n строк должны содержать координаты вершин в порядке обхода. Никакие три подряд идущие точки не должны лежать на одной прямой.