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