eolymp
bolt
Try our new interface for solving problems
Problems

Выпуклая оболочка

Выпуклая оболочка

Time limit 1 second
Memory limit 64 MiB

Вам дано множество точек на плоскости.

Найдите их выпуклую оболочку.

Input data

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

Output data

В первую строчку выходного файла выведите количество вершин в выпуклой оболочке. Во вторую - номера вершин через пробел, которые её образуют. Выведите вершины в порядке обхода против часовой стрелки. Никакие два ребра выпуклой оболочки не должны лежать на одной прямой.

В третью строчку выведите периметр оболочки, в четвертую - её площадь.

Периметр должен быть выведен с абсолютной или относительной погрешностью не больше 10^{-9}. Площадь должна быть выведена абсолютно точно.

Examples

Input example #1
9
0 0
1 1
2 2
1 0
0 1
2 0
0 2
2 1
1 2
Output example #1
4
3 7 1 6
8.00000000000000000000
4.0