Дано множество точек на плоскости. Найдите выпуклый многоугольник наименьшей площади, содержащий все эти точки.
Требуется получить два варианта ответа. В первом варианте вам нужно отобрать только те точки, которые окажутся в вершинах искомого многоугольника. Во втором варианте вам нужно отобрать все точки, которые окажутся на границе искомого многоугольника — и в вершинах, и на сторонах.
В первой строке входных данных записано целое число $$$n$$$ — количество точек ($$$3 \le n \le 10^5$$$).
В каждой из следующих $$$n$$$ строк записано по два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты очередной точки ($$$-10^9 \le x_i, y_i \le 10^9$$$).
Гарантируется, что никакие две точки не совпадают и существуют три точки, не лежащие на одной прямой.
В первой строке ответа выведите целое число $$$n_1$$$ — количество точек в вершинах многоугольника.
В каждой из следующих $$$n_1$$$ строк выведите пару целых чисел — координаты очередной точки в порядке обхода против часовой стрелки. Первой должна идти самая нижняя точка, а если таких несколько, то самая левая из них.
В следующей строке выведите целое число $$$n_2$$$ — количество точек в вершинах и на сторонах многоугольника.
В каждой из следующих $$$n_2$$$ строк выведите пару целых чисел — координаты очередной точки в порядке обхода против часовой стрелки. Аналогично, первой должна идти самая нижняя точка, а если таких несколько, то самая левая из них.
61 13 51 47 33 34 2
4 1 1 7 3 3 5 1 4 5 1 1 4 2 7 3 3 5 1 4
Иллюстрация к примеру из условия:
