Подразделы

Другие разделы

Дата и время

09/04/2025 11:05:08

Авторизация

Геометрия

Выпуклая оболочка Граница многоугольника Дуга на сфере Коза лесника Лабиринт Открытка и конверт Пересечение отрезков Пирамиды Площадь многоугольника Прямая и квадраты Стена Точки в многоугольнике Треугольник и точка

Граница многоугольника

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Многоугольник на плоскости задан целочисленными координатами своих

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

Ввод

В первой строке содержится число

$N\ (3\ ≤\ N\ ≤\ 100\ 000)$ , в следующих

$N$ строках – пары чисел – координаты точек. Координаты вершин целые и по модулю не превосходят

$10^9$ . Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

Вывод

Вывести одно число – количество точек с целочисленными координатами на границе многоугольника.

Пример ввода

Пример вывода

Источник: отборочный тур ВГПУ, 2001, Меньшиков