Pick 정리는 꼭짓점이 격자점 (integer lattice) 위에 있는 단순 다각형의 넓이 A 를 내부 격자점 개수 I 와 경계 격자점 개수 B 로 표현: A = I + B/2 - 1. 1899년 오스트리아 수학자 Georg Pick 이 발견.
문제 상황과 동기
격자점 다각형의 넓이를 구할 때, 내부 점과 경계 점의 개수만 세면 넓이를 알 수 있음.
Naive 접근: 다각형을 삼각형 분할 후 면적 합산. 분할 자체가 복잡하고 일반화 어려움.
핵심 통찰: 격자점의 개수만으로 단순한 공식 A = I + B/2 - 1. 신발끈 공식 으로 면적을 구한 후 역으로 I 를 계산하기도 함.
PS 위치: 좌표 범위가 작고 격자점이 명시적인 문제. 내부 점 개수만 묻는 문제에 직접 활용.
시각화
핵심 아이디어
A = I + B/2 - 1A: 다각형 넓이I: 내부 격자점 개수 (경계 제외)B: 경계 위 격자점 개수경계 격자점 계산 (각 변): dx = |x2 - x1|, dy = |y2 - y1| 기여 = gcd(dx, dy) # (0,0) 포함, (x2,y2) 미포함 합계면적을 알 때 내부 점: I = A - B/2 + 1
알고리즘
boundary_points(vertices): B = 0 for i = 0..N-1: j = (i+1) % N dx = |vertices[i].x - vertices[j].x| dy = |vertices[i].y - vertices[j].y| B += gcd(dx, dy) return Barea_from_pick(I, B): return I + B/2 - 1
구현
// Pick 정리: 격자점 다각형의 넓이 = I + B/2 - 1#include <bits/stdc++.h>using namespace std;using ll = long long;struct Pt { ll x, y; };ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }ll shoelace2(const vector<Pt>& p) { ll a2 = 0; for (int i = 0; i < (int)p.size(); i++) { int j = (i+1) % p.size(); a2 += p[i].x * p[j].y - p[j].x * p[i].y; } return abs(a2); // 2*A}ll boundary(const vector<Pt>& p) { ll B = 0; for (int i = 0; i < (int)p.size(); i++) { int j = (i+1) % p.size(); B += gcd(abs(p[i].x-p[j].x), abs(p[i].y-p[j].y)); } return B;}int main() { int N; cin >> N; vector<Pt> p(N); for (auto& pt : p) cin >> pt.x >> pt.y; ll A2 = shoelace2(p); ll B = boundary(p); ll I = (A2 - B + 2) / 2; cout << "Area: " << A2/2; if (A2 % 2) cout << ".5"; cout << "\nBoundary: " << B << "\nInterior: " << I << "\n";}
from math import gcddef shoelace2(p): a2 = 0 for i in range(len(p)): j = (i+1) % len(p) a2 += p[i][0]*p[j][1] - p[j][0]*p[i][1] return abs(a2)def boundary(p): B = 0 for i in range(len(p)): j = (i+1) % len(p) B += gcd(abs(p[i][0]-p[j][0]), abs(p[i][1]-p[j][1])) return BN = int(input())p = [tuple(map(int, input().split())) for _ in range(N)]A2 = shoelace2(p)B = boundary(p)I = (A2 - B + 2) // 2area = A2 // 2print(f"Area: {area}" + (".5" if A2 % 2 else ""))print(f"Boundary: {B}\nInterior: {I}")
import java.util.*;import java.io.*;public class Main { static long gcd(long a, long b) { return b==0 ? a : gcd(b, a%b); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); long[] x = new long[N], y = new long[N]; for (int i=0; i<N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); x[i] = Long.parseLong(st.nextToken()); y[i] = Long.parseLong(st.nextToken()); } long A2 = 0, B = 0; for (int i=0; i<N; i++) { int j = (i+1) % N; A2 += x[i]*y[j] - x[j]*y[i]; B += gcd(Math.abs(x[i]-x[j]), Math.abs(y[i]-y[j])); } A2 = Math.abs(A2); long I = (A2 - B + 2) / 2; System.out.print("Area: " + A2/2); if (A2%2==1) System.out.print(".5"); System.out.println("\nBoundary: " + B + "\nInterior: " + I); }}
stdin
40 03 03 40 4
결과
Area: 12Boundary: 12Interior: 7
stdin
30 06 00 8
결과
Area: 24Boundary: 12Interior: 19
복잡도
항목
값
Shoelace 면적
O(N)
B 계산 (gcd)
O(N log M)
전체
O(N log M)
변형 / 활용
역 Pick: 면적 A 와 B 를 알 때 I = A - B/2 + 1.
Ehrhart theory: 고차원 격자점 다각형 일반화.
응용: GIS 영역 분석, 화면 픽셀 커버리지.
함정
1. .5 단위 넓이
B 가 홀수면 A 는 .5 단위. 정수형만 사용할 때 shoelace 의 2 배 값 (A2) 을 유지해야 손실 없음.
2. 단순 다각형 조건
자기 교차 (self-intersecting) 또는 구멍이 있는 다각형에서는 성립하지 않음.
3. GCD 경계 계산
dx=0 또는 dy=0 인 수평/수직 변은 gcd(0, k) = k. 변의 양 끝점 중 한쪽만 세도록 처리.
💬 댓글