Задача №680. Точки в многоугольнике
Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти число точек с целочисленными координатами, лежащих внутри многоугольника (не на границе). Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.
Ограничения: 3 <= N <= 10 000, координаты вершин целые и по модулю не превосходят 1 000 000.
Входные данные
В первой строке находится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Выходные данные
Вывести одно число - искомое количество точек.
Примеры
Входные данные
3 1 0 0 0 0 1
Выходные данные
0
Сдать: для сдачи задач необходимо войти в систему