Выпуклая оболочка
Вам дано множество точек на плоскости.
Найдите их выпуклую оболочку.
Входные данные
Первая строка входного файла содержит целое число n - количество точек (3 ≤ n ≤ 200000). В следующих n строках описываются точки. i-я строка состоит из двух целых чисел - координат i-й точки. Координаты не превосходят 10^9 по модулю. Гарантируется, что все точки не лежат на одной прямой. Точки могут совпадать.
Выходные данные
В первую строчку выходного файла выведите количество вершин в выпуклой оболочке. Во вторую - номера вершин через пробел, которые её образуют. Выведите вершины в порядке обхода против часовой стрелки. Никакие два ребра выпуклой оболочки не должны лежать на одной прямой.
В третью строчку выведите периметр оболочки, в четвертую - её площадь.
Периметр должен быть выведен с абсолютной или относительной погрешностью не больше 10^{-9}. Площадь должна быть выведена абсолютно точно.