Задачи
Точки в многоугольнике
Точки в многоугольнике
Многоугольник на плоскости задан целочисленными координатами своих n вершин в декартовой системе координат. Найти количество точек с целочисленными координатами, лежащих внутри многоугольника (не на границе). Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.
Входные данные
В первой строке находится число n, в следующих n строках - пары чисел - координаты точек (3 ≤ n ≤ 10000, координаты вершин целые и по модулю не превосходят 1000000). Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.
Выходные данные
Вывести одно число - искомое количество точек.
Входные данные #1
4 -10 -10 -10 10 10 10 10 -10
Выходные данные #1
361