eolymp
bolt
Try our new interface for solving problems
Məsələlər

Точки в многоугольнике

Точки в многоугольнике

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

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

В первой строке находится число n, в следующих n строках - пары чисел - координаты точек (3n10000, координаты вершин целые и по модулю не превосходят 1000000). Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4
-10 -10
-10 10
10 10
10 -10
Çıxış verilənləri #1
361