Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
23. Границы многоугольника
Вычислительная геометрияИспользование теорем из геометрии, формулы Пика
Олимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 8D) |
| 19/07/2006 | Лето 2006 - 8 (D) |
| 29/06/2020 | Летние сборы 1 (A) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Многоугольник на плоскости задан целочисленными координатами своих `N` вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних – в вершинах) и не пересекаются.
Ввод
В первой строке содержится число `N\ (3\ ≤\ N\ ≤\ 100\ 000)`, в следующих `N` строках – пары чисел – координаты точек. Координаты вершин целые и по модулю не превосходят `10^9`. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Вывод
Вывести одно число – количество точек с целочисленными координатами на границе многоугольника.
Пример ввода
3 10 0 0 10 0 0
Пример вывода
30
