Граница многоугольника
(Время: 1 сек. Память: 16 Мб Сложность: 36%)
Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат.
Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних – в вершинах) и не пересекаются.
Входные данные
Первая строка входного файла INPUT.TXT содержит число N (3 ≤ N ≤ 105), в следующих N строках записаны пары чисел – координаты точек (целые числа, не превосходящие 109 по абсолютной величине). Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – количество точек с целочисленными координатами на границе многоугольника.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
10 0
0 10
0 0 | 30 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
