Problems
Polygon
Polygon
Многоугольник состоит из n вершин и лежит на бесконечной прямоугольной сетке. Все вершины многоугольника имеют целочисленные координаты. Стороны данного многоугольника не пересекаются. Необходимо найти общую длину линейных сегментов сетки, которые лежат строго в заданном многоугольнике (см. рисунки ниже).
Входные данные
В первой строке содержится число n (3 ≤ n ≤ 100 000). В каждой из следующих n строк содержатся два целых числа − координаты вершин многоугольника (-5∙108
≤ x, y ≤ 5∙108
). Координаты задаются в порядке обхода или по, или против часовой стрелки.
Выходные данные
Вывести одно число (с точностью до 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
Input example #1
3 5 1 2 4 1 1
Output example #1
10.000