Граница многоугольника
Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.
Ограничения: 3 <= N <= 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000.
Входные данные
В первой строке содержится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Выходные данные
Вывести одно число - количество точек с целочисленными координатами на границе многоугольника.
Примеры
Входные данные
8 5 15 15 5 15 -5 5 -15 -5 -15 -15 -5 -15 5 -5 15
Выходные данные
80
algoprog.ru © Петр Калинин, GNU AGPL, github.com/petr-kalinin/algoprog | О лицензии на материалы сайта | Блог