Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).
Входные данные
В первой строке вводится N (3≤N≤1000) – число вершин многоугольника. В последующих N строках идут координаты (X
i, Y
i) вершин многоугольника в порядке обхода по часовой стрелке. X
i и Y
i – целые числа, по модулю не превосходящие 10
6.
Выходные данные
Вывести одно число – искомое количество точек.
Примеры
№ | Входные данные | Выходные данные |
1
|
3 0 0 6 2 4 0
|
1
|