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