Точки в многоугольнике

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

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

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

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

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

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

Пример

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

[Обсуждение] [Все попытки] [Лучшие попытки]