Начало
ЗадачиПодразделы
Другие разделы
Дата и время
17/11/2024 09:18:13
Геометрия
Выпуклая оболочка Граница многоугольника Дуга на сфере Коза лесника Лабиринт Открытка и конверт Пересечение отрезков Пирамиды Площадь многоугольника Прямая и квадраты Стена Точки в многоугольнике Треугольник и точка
Точки в многоугольнике
Вычислительная геометрияИспользование теорем из геометрии, формулы Пика
Олимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 9D) |
| 24/07/2006 | Лето 2006 - 9 (нет результатов) (D) |
| 14/03/2009 | Занятие 15 (D) |
| 16/04/2014 | Занятие 21 (C) |
| 17/03/2015 | Занятие 17 (B) |
| 07/10/2023 | Тренировка 1 (проводит gribanov) (U) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Многоугольник на плоскости задан целочисленными координатами своих `N` вершин в декартовой системе координат. Требуется найти число точек с целочисленными координатами, лежащих внутри многоугольника (не на границе). Стороны многоугольника друг с другом не соприкасаются (за исключением соседних – в вершинах) и не пересекаются.
Ограничения: `3\ ≤\ N\ ≤\ 10\ 000`, координаты вершин целые и по модулю не превосходят `1\ 000\ 000`.
Ввод
В первой строке находится число `N`, в следующих `N` строках – пары чисел – координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Вывод
Вывести одно число – искомое количество точек.
Пример ввода
4 -10 -10 -10 10 10 10 10 -10
Пример вывода
361
