Формула Пика
Пусть у нас есть многоугольник $A_1 A_2 \ldots A_n$, такой что координаты $A_i$ целые для всех $1 \leq i \leq n$. Обозначим за $S$ площадь многоугольника, за $В$ количество целых точек строго внутри многоугольника, за $Г$ количество целых точек на границе многоугольника (сами вершины тоже считаются). Тогда утверждается, что выполнено следующее равенство $S = В + \frac{Г}{2} - 1$.
Для доказательства заметим, что если формула верна для двух многоугольников, имеющих общую сторону, то для их объединения тоже верна. Это так, потому что $(В_1 + \frac{Г_1}{2} - 1) + (В_2 + \frac{Г_2}{2} - 1) = (B_1 + B_2) + \frac{Г_1 + Г_2}{2} - 2$. Точки, которые были внутри одного из двух многоугольников, остались внутри. Точки, которые были на границе одного из двух многоугольников, если они не лежали на отрезке общей стороны, то останутся на границе и действительно посчитаются $1$ раз. Точки, лежащие на общей стороне, которые не совпадают с концами отрезка, теперь станут внутренними, но заметим, что они посчитаются с коэфициентами $\frac{1}{2}$ в каждом из многоугольников, поэтому их коэфициент будет равен $1$. Две точки, концы общего отрезка, останутся на границе, но теперь внесут вклад $2$ в сумму, а должны $1$. Но заметим, что у нас вычитается $-2$, и сократив $1$, мы получим, что $S_1 + S_2 = В + \frac{Г}{2} - 1$. Таким образом мы можем доказать для треугольника и тогда мы докажем для всех многоугольников, потому что любой многоугольник можно триангулировать. Чтобы доказать для треугольника можно заметить, что треугольник можно разбить на прямоугольные треугольники, для которых формула Пика очевидна.
Заметим, что теперь по многоугольнику мы можем посчитать количество целых точек внутри, потому что площадь мы можем вычислить за линейное время и остается вычислить количество точек на границе мноугольника. Заметим, что на отрезке, соединяющем точки с координатами $(x_1, y_1)$ и $(x_2, y_2)$ лежит $1 + gcd(|x_1 - x_2|, |y_1 - y_2|)$ точек. Поэтому мы можем просто просуммировать эти величины по всем сторонам (не забывайте, что концы посчитаются по $2$ раза) и получим $Г$. Тогда из формулы Пика мы получим $В$.
Автор конспекта: Иван Сафонов
По всем вопросам пишите в telegram @isaf27