Заочный тур Московской городской олимпиады школьников по программированию

Задача "Целые точки"

Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).

Формат входных данных

В первой строке содержится N (3≤N≤1000) - число вершин многоугольника. В последующих N строках идут координаты (Xi, Yi) вершин многоугольника в порядке обхода по часовой стрелке. Xi и Yi - целые числа, по модулю не превосходящие 1000000.

Формат выходных данных

В выходной файл вывести одно число - искомое число точек.

Примеры

e.in e.out
4
-1 -1
-1 1
1 1
1 -1
1
3
0 0
0 2
2 0
0