Республиканская олимпиада по информатике 2008 года за 11 класс | Казахстанские олимпиады

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

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

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

Первая строка входного файла содержит целое число $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