홍라이프 계산기픽의 정리 계산기 쉽게 이해하기 — 개념과 원리
픽의 정리는 모눈종이 위에 그린 다각형의 넓이를 점의 개수만 세어 구하는 방법입니다. 다각형의 모든 꼭짓점이 격자점(좌표가 모두 정수인 점) 위에 있다면, 다각형 내부에 있는 격자점의 개수 I와 경계 위에 있는 격자점의 개수 B만 알면 됩니다. 수학 경시대회에 자주 나오며, 신발끈 공식으로 구한 넓이를 검산하거나 모눈종이와 픽셀 격자 위 도형의 넓이를 잴 때 편리합니다.
계산 방법
A = I + B/2 − 1
- I(내부 격자점): 다각형의 안쪽에 있는 격자점의 개수
- B(경계 격자점): 변 위에 있는 격자점의 개수(꼭짓점 포함)
넓이의 단위는 모눈 한 칸입니다. 격자 간격이 1 cm이면 넓이는 cm²입니다. (x₁, y₁)에서 (x₂, y₂)까지의 변 위에 있는 격자점은 한쪽 끝점을 포함해 gcd(|x₂ − x₁|, |y₂ − y₁|)개이므로, 모든 변에 대해 더하면 B가 됩니다.
원리
격자점 하나가 주변 넓이를 일정 몫씩 나누어 가진다고 생각해 보십시오. 내부의 점은 한 칸 전체를, 곧은 변 위의 점은 주변의 절반만 다각형 안에 있으므로 ½을 가져갑니다. 꼭짓점에서는 몫이 딱 맞지 않는데, 다각형을 한 바퀴 돌 때 외각의 합이 360°, 즉 한 바퀴이고 이만큼이 정확히 한 칸에 해당하므로 1을 뺍니다. 엄밀한 증명은 다른 격자점을 포함하지 않는 삼각형(넓이 ½)에서 식이 성립하고, 다각형을 변을 따라 붙여도 식이 유지됨을 보이는 방식입니다. 게오르크 픽이 1899년에 발표했습니다.
예제 풀이
- 입력값은 I = 7, B = 8입니다.
- 경계 격자점의 절반은 8 ÷ 2 = 4입니다.
- 넓이는 7 + 4 − 1 = 10입니다.
- 이런 다각형의 예로 삼각형 (0, 0), (0, 5), (4, 2)가 있습니다. 세 변의 경계점은 5 + 2 + 1 = 8개이고, 신발끈 공식으로도 넓이가 |0×5 − 4×5| ÷ 2 = 10입니다.
| 내부 격자점 I | 넓이 |
|---|---|
| 1.75 | 4.75 |
| 3.5 | 6.5 |
| 5.25 | 8.25 |
| 7 | 10 |
| 8.75 | 11.75 |
| 10.5 | 13.5 |
| 14 | 17 |
결과 해석
격자 다각형의 넓이는 B/2 때문에 항상 정수이거나 정수에 0.5를 더한 값입니다. B가 홀수이면 넓이는 .5로 끝납니다. 검산 예로, 가로 4, 세로 3인 직사각형은 B = 14, I = 6이므로 A = 6 + 7 − 1 = 12입니다.
흔한 실수
- B를 셀 때 꼭짓점을 빠뜨리거나 두 번 세는 경우입니다.
- 변 위에 있는 점을 내부 점으로 세는 경우입니다.
- 꼭짓점이 격자점 위에 있지 않은 도형에 적용하는 경우입니다.
자주 묻는 질문
구멍이 있는 다각형은 어떻게 하나요?
구멍이 h개이면 A = I + B/2 + h − 1이 됩니다.
삼각형 격자에도 쓸 수 있나요?
이 형태 그대로는 쓸 수 없습니다. 정사각형 정수 격자를 기준으로 한 정리입니다.
경계 격자점을 빨리 세는 방법은요?
변마다 x좌표 차와 y좌표 차의 최대공약수를 구해 모두 더하면 됩니다.
출처: G. Pick, Geometrisches zur Zahlenlehre, Sitzungsberichte des deutschen naturwissenschaftlich-medicinischen Vereines für Böhmen “Lotos” in Prag 19 (1899), 311–319 · J. E. Reeve, On the volume of lattice polyhedra, Proceedings of the London Mathematical Society (1957)