Многоугольник
Многоугольник состоит из n вершин и лежит на бесконечной прямоугольной сетке. Все вершины многоугольника имеют целочисленные координаты. Стороны данного многоугольника не пересекаются. Необходимо найти общую длину линейных сегментов сетки, которые лежат строго в заданном многоугольнике (см. рисунки ниже).
Входные данные
В первой строке содержится число n (3 ≤ n ≤ 100 000). В каждой из следующих n строк содержатся два целых числа − координаты вершин многоугольника (-5∙10^8 ≤ x, y ≤ 5∙10^8). Координаты задаются в порядке обхода или по, или против часовой стрелки.
Выходные данные
Вывести одно число (с точностью до 3 знаков после десятичной точки) − общую длину линейных сегментов сетки, которые лежат строго в заданном многоугольнике.
Пояснение к первому тесту
Суммарная длина горизонтальных линий: 4/3 + 8/3 = 4
Суммарная длина вертикальных линий: 3 + 2 + 1 = 6
Поэтому общая длина равна 4 + 6 = 10
Пояснение ко второму тесту
Суммарная длина горизонтальных линий: 1 + 2 + 4 = 7
Суммарная длина вертикальных линий: 9/4 + 3/2 + 7/4 = 5.5
Поэтому общая длина равна 7 + 5.5 = 12.5