Задача W. Забор в парке

Автор:И. Лудов, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

В бесконечном квадратном парке деревья образуют квадратную решётку с шагом 1 метр. Часть парка было решено оградить забором, который представляет собой многоугольник с заданными координатами вершин. Деревья, которые в точности попадают на вершины или стороны многоугольника, придётся срубить. Необходимо выяснить количество таких деревьев.

Программа должна, получив на входе число вершин многоугольника N и их целочисленные координаты (x1, y1), …, (xN, yN), определить количество точек с целочисленными координатами, лежащих на границе этого многоугольника.

Стороны многоугольника не самопересекаются.

Формат входного файла

Входной файл содержит число N, за которым следует N пар координат x1 y1xN yN

Формат выходного файла

Выходной файл должен содержать единственное число — количество точек.

Ограничения

3 ≤ N ≤ 1000, 0 ≤ xi, yi ≤ 107, исходные данные таковы, что результат не превосходит 231−1.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
0 0 2 0 0 2
6

0.183s 0.025s 13