Олимпиадный тренинг

Задача . Граница многоугольника


Задача

Темы: НОД и алгоритм Евклида
Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.

Ограничения: 3 <= N <= 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000.

Входные данные
В первой строке содержится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

Выходные данные
Вывести одно число - количество точек с целочисленными координатами на границе многоугольника.
Примеры
№Входные данныеВыходные данные
1 
8
5 15
15 5
15 -5
5 -15
-5 -15
-15 -5
-15 5
-5 15

80
Статистика успешных решений по компиляторам
 Кол-во
Python1
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет