Archive - Забор в парке

Забор в парке ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

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

Программа должна, получив на входе число вершин многоугольника N и их целочисленные координаты (x₁, y₁), …, (x_N, y_N), определить количество точек с целочисленными координатами, лежащих на границе этого многоугольника.

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

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

Входной файл содержит число N, за которым следует N пар координат x₁ y₁ … x_N y_N

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

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

Ограничения

3 ≤ N ≤ 1000, 0 ≤ x_i, y_i ≤ 10⁷, исходные данные таковы, что результат не превосходит 2³¹−1.

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

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