Начало
ЗадачиПодразделы
Другие разделы
Дата и время
17/11/2024 09:20:27
Геометрия
Выпуклая оболочка Граница многоугольника Дуга на сфере Коза лесника Лабиринт Открытка и конверт Пересечение отрезков Пирамиды Площадь многоугольника Прямая и квадраты Стена Точки в многоугольнике Треугольник и точка
Граница многоугольника
Вычислительная геометрияИспользование теорем из геометрии, формулы Пика
Олимпиадные задачи на русском языке
| 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
