그린 정리 (Green's Theorem)

정의

그린 정리 (Green’s Theorem) 는 평면 위의 폐곡선 C 에 대한 선적분(line integral) 과 그 내부 영역 D 에 대한 이중 적분(double integral) 을 연결: ∮_C (L dx + M dy) = ∬_D (∂M/∂x - ∂L/∂y) dA. 곡선 C 는 반시계 방향(counterclockwise)으로 양의 방향.

문제 상황과 동기

폐곡선으로 둘러싸인 영역의 넓이를 선적분만으로 계산.

• Naive 접근: 영역을 작은 사각형으로 분할해 Riemann 합. mesh size 에 의존.
• 핵심 통찰: Green 정리의 특수한 경우: ∮_C x dy = area(D). 즉, 경계선을 따라 x dy 만 적분하면 면적.
• PS 위치: 신발끈 공식 이 Green 정리의 이산 버전. 다각형의 면적 O(N). 좌표 기하 문제에서 면적을 직접 계산해야 할 때.

시각화

핵심 아이디어

Green 정리 (일반):
  ∮_C (L dx + M dy) = ∬_D (∂M/∂x - ∂L/∂y) dA

면적 공식 (L = -y/2, M = x/2):
  Area(D) = ∮_C (x dy - y dx) / 2 = ∮_C x dy

다각형 면적 (Shoelace, 이산 버전):
  Area = (1/2) * | Σ (x_i * y_{i+1} - x_{i+1} * y_i) |

증명 스케치: ∂M/∂x - ∂L/∂y 가 1 이 되도록 L, M 을 잡으면 우변은 area.

알고리즘

polygon_area(vertices[0..N-1]):
    area2 = 0
    for i = 0..N-1:
        j = (i+1) % N
        area2 += vertices[i].x * vertices[j].y
        area2 -= vertices[j].x * vertices[i].y
    return abs(area2) / 2.0

구현

// Green 정리 기반 shoelace 공식으로 다각형 면적
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Pt { ll x, y; };
int main() {
  int n; cin >> n;
  vector<Pt> p(n);
  for (auto& v : p) cin >> v.x >> v.y;
  ll area2 = 0;
  for (int i = 0; i < n; i++) {
      int j = (i + 1) % n;
      area2 += p[i].x * p[j].y;
      area2 -= p[j].x * p[i].y;
  }
  area2 = abs(area2);
  cout << "Area: " << area2 / 2;
  if (area2 % 2) cout << ".5";
  cout << "\n";
}

# Green 정리로 다각형 면적 (shoelace)
def polygon_area(p):
  area2 = 0
  n = len(p)
  for i in range(n):
      j = (i + 1) % n
      area2 += p[i][0] * p[j][1] - p[j][0] * p[i][1]
  area2 = abs(area2)
  area = area2 // 2
  return area, area2 % 2
n = int(input())
p = [tuple(map(int, input().split())) for _ in range(n)]
area, half = polygon_area(p)
print(f"Area: {area}" + (".5" if half else ""))

import java.util.*;
import java.io.*;
public class Main {
  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;
      for (int i = 0; i < n; i++) {
          int j = (i + 1) % n;
          a2 += x[i] * y[j] - x[j] * y[i];
      }
      a2 = Math.abs(a2);
      System.out.print("Area: " + a2 / 2);
      if (a2 % 2 == 1) System.out.print(".5");
      System.out.println();
  }
}

4
0 0
4 0
4 3
0 3

Area: 12

3
0 0
6 0
0 8

Area: 24

5
0 0
5 0
6 3
2 5
-1 2

Area: 24

복잡도

변형 / 활용

• Shoelace (신발끈 공식): Green 정리의 이산 버전. 정수 좌표 다각형의 면적.
• Stokes 정리: 3차원 일반화. Green 은 Stokes 의 2D 특수 케이스.
• 발산 정리 (Divergence Theorem): ∮ F·n ds = ∬ div F dA (flux form).
• 응용: 유체 역학에서 circulation, CAD 에서 면적 계산, GIS.

함정

1. 방향

시계 방향(clockwise) 입력이면 면적이 음수. 반드시 abs() 처리.

2. 정수 좌표 .5 문제

면적이 2 로 나누어떨어지지 않으면 .5 단위. 코드에서 area2 (2배 값) 를 유지해야 정밀도 손실 없음.

3. 자기 교차 다각형

자기 교차하는 폴리곤은 Green 정리의 단순 폐곡선 조건을 만족하지 않음. signed area 개념으로 확장 가능.

BOJ 연습 문제

참고

• 신발끈 공식
• Pick 정리
• 기하 기본