Республиканская олимпиада по информатике 2008 год

Задача F. Многоугольник

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайт

От вас требуется посчитать, сколько точек с целочисленными координатами лежит внутри или на границе заданного простого многоугольника. Стороны многоугольника не пересекаются.

Формат входного файла

Первая строка входного файла содержит целое число $N$ (1 <= $N$ <= $10^5$). Следующие $N$ строк содержат по два вещественных числа по модулю не превышающих 10000 и имеющих не более чем три знака после запятой — (x, y) координаты точек многоугольника в порядке обхода (x, y не целые). Периметр многоугольника не превышает $10^6$ (1,000,000). Числа в строках разделены пробелами.

Формат выходного файла

Выходной файл должен содержать одно целое число — ответ на задачу.

Пример:

Вход

3
14.815 43.958
21.457 34.883
21.802 50.559

Ответ

48