꼭짓점 $A_i$의 좌표가 모든 $1 \leq i \leq n$에 대해 정수인 다각형 $A_1 A_2 \ldots A_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$번씩 세어진다는 점을 잊지 마십시오) $Г$를 얻습니다. 그러면 픽의 공식으로부터 $В$를 얻습니다.

분류:강의 노트