Страница: 1 Отображать по:

#496

Точки

Темы: [Элементарная геометрия]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2007, 2 день, Задача C ]

Петя и Вася играют в "точки". Петя отметил на клетчатом листе бумаги несколько точек – узлов сетки. Вася хочет окружить их многоугольником так, чтобы все отмеченные узлы лежали строго внутри (не на границе) этого многоугольника и чтобы все стороны этого многоугольника проходили только по сторонам или диагоналям клеток сетки, а его периметр был минимально возможным. Определите, чему равен периметр такого многоугольника.

Входные данные

В первой строке входных данных содержится число N – количество отмеченных Петей точек (1 ≤ N ≤ 100 000).

В каждой из следующих N строк записаны по два числа x_i, y_i – координаты точек, нарисованных Петей. Координаты по абсолютной величине не превосходят 10⁶. Некоторые точки могут совпадать.

Выходные данные

Требуется вывести одно число – периметр искомого многоугольника. Ответ нужно вывести с точностью не менее 0.001.

Примеры

Входные данные

1
0 0

Выходные данные

5.6568542495

Входные данные

2
1 1
1 2

Выходные данные

7.6568542495

Страница: 1 Отображать по:

Выбрано

Отменить

Добавить в контест