Целочисленные многоугольники
Целочисленные многоугольники
Ингрид держит многоугольный магазин в далекой стране. Она продает только выпуклые многоугольники с целыми координатами. Ее клиенты предпочитают многоугольники, которые можно правильно разрезать на две половины, то есть разрез должен быть прямым с начальной и конечной точками в вершинах многоугольника, а обе половины должны быть непустыми и иметь целочисленную площадь. Чем больше способов правильно разрезать многоугольник - тем он дороже.
Например, имеется три способа разрезать левый многоугольник правильным образом и два способа - правый многоугольник.
Многоугольники в магазине всегда отличного качества, поэтому бизнес расширяется. Теперь Ингрид нужен какой-то автоматический инструмент, чтобы определить количество способов правильного разрезания многоугольника. Это очень важно для ее магазина, иначе Вы потратите много времени на установление цен - только представьте, сколько времени потребуется, чтобы установить цену на фургон среднего размера с многоугольниками. Не могли бы Вы помочь Ингрид и написать для нее программу?
Входные данные
В первой строке записано целое число n (4 ≤ n ≤ 200 000) - количество вершин многоугольника. Каждая из следующих n строк содержит координаты вершин: пару целых чисел xi
и yi
(-109
≤ xi
, yi
≤ 109
) в строке.
Указанный многоугольник выпуклый, а его вершины указаны в порядке обхода.
Выходные данные
Выведите одно целое число w - количество способов разрезать многоугольник правильным образом.
5 7 3 3 5 1 4 2 1 5 0
3
4 1 1 3 1 5 5 1 3
2