Петя и Вася играют в "точки". Петя отметил на клетчатом листе бумаги несколько точек – узлов сетки. Вася хочет окружить их многоугольником так, чтобы все отмеченные узлы лежали строго внутри (не на границе) этого многоугольника и чтобы все стороны этого многоугольника проходили только по сторонам или диагоналям клеток сетки, а его периметр был минимально возможным. Определите, чему равен периметр такого многоугольника.
Входные данные
В первой строке входных данных содержится число N – количество отмеченных Петей точек (1 ≤ N ≤ 100 000).
В каждой из следующих N строк записаны по два числа x
i, y
i – координаты точек, нарисованных Петей. Координаты по абсолютной величине не превосходят 10
6. Некоторые точки могут совпадать.
Выходные данные
Требуется вывести одно число – периметр искомого многоугольника. Ответ нужно вывести с точностью не менее 0.001.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
0 0
|
5.6568542495
|
|
2
|
2
1 1
1 2
|
7.6568542495
|