Суммарная длина целочисленной сетки внутри многоугольника

[fractalon]

На плоскости задан произвольный многоугольник без самопересечений (однако не обязательно выпуклый). Вершин у многоугольника до ${10}^{5}$ и координаты всех вершин целые.
Задаётся прямоугольник простым перечислением вершин в том порядке, в котором они в нём связаны.

Рассмотрим бесконечную целочисленную сетку на плоскости, то есть сетку с узлами в точках с целыми координатами, линии которой идут по точкам, хотя бы одна из координат которых цела. Короче, обычную сетку из квадратиков с узлами в целых точках.
Требуется для заданного многоугольника найти суммарную длину линий сетки, которые лежат внутри этого многоугольника.

Я, кажется, основную идею просёк. Задача вполне тривиальна для прямоугольника и для прямоугольного треугольника (если включать в суммарную длину также длины сторон многоугольника, лежащих ровно на линии сетки - а это кажеться удобным делать, потом их всё равно можно вычесть за один проход). Воспользовавшись этим можно также посчитать ответ для выпуклого многоугольника (потому что это суть прямоугольник, из которого повычитали прямоугольники и прямоугольные треугольники).

Остаётся последний вопрос: как разложить произвольный многоугольник на сумму выпуклых? Интуитивно ясно, что такое разложение всегда существует, и на коленке даже можно набросать какие-то алгоритмы, но получается криво и громоздко. Прошу подсказки по поводу каких-то общих техник - наверняка случай возникновения этой задачи не единичен.

[worm2]

Если договориться, что линия сетки, лежащая ровно на границе многоугольника, считается с половинным коэффициентом, то ответ на вопрос задачи — это удвоенная площадь многоугольника. Доказывается так, как Вы написали: сначала для прямоугольника, потом для прямоугольного треугольника, затем как бы ни разбивался многоугольник на прямоугольные треугольники, результат всё равно один и тот же.

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

[fractalon]

Ух ты как! Хитро... Очень поучительная задачка. То есть решение - это площадь минус половина длины сторон многоугольника на сетке...
Выходит, задача свелась к нахождению площади многоугольника. А как находить её теперь? Опять же, для выпуклого более-менее можно что-то придумать, а для произвольного непонятно... Всё равно придётся, значит, раскладывать в сумму выпуклых?
Из весёлых приёмчиков знаю только теорему Пика, но там нужно количество целых точек внутри. А это количество находить, кажется, не менее сложно, чем площадь.

[worm2]

Если честно, я от Вас узнал про теорему Пика. Это слишком сложно. Выражение для площади многоугольника через координаты его вершин очень простое. И годится для любого несамопересекающегося многоугольника (не обязательно с целочисленными координатами).
Я так думаю, олимпиадники должны эту формулу знать, ибо без неё тяжко.
Вот, в Википедии она есть.