Целые точки

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

Технические условия

Входные данные

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

Выходные данные

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

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 31% 70/102
Классификация: Теория чисел, НОД, НОК

Пример

Пример входных данных

Sample 1
4
-1 -1
-1 1
1 1
1 -1

Sample 2
3
0 0
0 2
2 0

Пример выходных данных

Sample 1
1

Sample 2
0

← Клад

Список задач