Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 36%)

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

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

Входные данные

Первая строка входного файла INPUT.TXT содержит число N (3 ≤ N ≤ 105), в следующих N строках записаны пары чисел – координаты точек (целые числа, не превосходящие 109 по абсолютной величине). Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

Выходные данные

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

Пример

INPUT.TXTOUTPUT.TXT
13
10 0
0 10
0 0
30

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Олимпиадные задачи по программированию, 2006
 Тренировка 1
 Тренировка 2
 Тренировка 3
 Тренировка 4
 Тренировка 5
 Тренировка 6
 Тренировка 7
 Тренировка 8
 Тренировка 9
 Тренировка 10
 Тренировка 11
 Тренировка 12
 Тренировка 13
 Тренировка 14
 Тренировка 15
 A. Анти-QuickSort
 B. Строки Фибоначчи
 C. Игра в зачеркивание
 D. Граница многоугольника
 E. Путь спелеолога
 F. Дырявая ткань

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru