BOJ 17441. 파리채 만들기

▣ 문제 출처  ─  2019년도 서울대학교 프로그래밍 경시대회(SNUPC) Div. 1 G번 문제

▣ 알고리즘 분류  ─  수학(미적분학, 기하학, 확률론)

▣ solved.ac 기준 난이도  ─  Diamond II

 

 

문제의 내용은 여기에서 볼 수 있다.

 

  필요하지 않은 스토리텔링 부분을 제외하면 문제의 내용은 한 줄로 요약할 수 있다: 다각형이 주어질 때, 다각형 내의 임의의 두 점 사이 거리의 제곱의 기댓값을 구하는 것이 목표다.

 

  다각형 내의 점은 연속적으로 분포하므로 적분을 써야한다는 것을 쉽게 짐작할 수 있다. 주어지는 다각형의 전체 넓이(혹은 다각형 그 자체)를 $S$라고 하자. 두 점의 좌표를 각각 $(x_1,\, y_1),\, (x_2,\, y_2)$라 하면 거리의 제곱은 $(x_1 - x_2)^2 + (y_1 - y_2)^2$가 되고, 두 점 근방에서 미소면적 $dA_1 = dx_1 dy_1,\, dA_2 = dx_2 dy_2$를 잡았을 때 전체 다각형 영역 중에서 각 미소면적 내의 점을 독립적으로 하나씩 택할 확률은 $\dfrac{dA_1 dA_2}{S^2}$가 된다.

 

따라서 기댓값 $E$는 다음의 적분식으로 계산할 수 있다.

$$\begin{aligned}​E &= \frac{1}{S^2}\iint_S \iint_S (x_1 - x_2)^2 + (y_1 - y_2)^2\,dA_1\,dA_2 \\ &= \frac{1}{S^2}\iint_S \iint_S \left(x_1^2 +x_2^2 - 2x_1 x_2 + y_1^2 + y_2^2 -2y_1 y_2 \right) dA_1\,dA_2\end{aligned}​$$

 

보기만 해도 굉장히 불쾌해지는 모양의 식이지만, 꾹 참고 조금 더 건드려 보자.

 

• $\displaystyle\iint_S \iint_S x_1^2\,dA_1\,dA_2 = \left(\iint_S x^2\,dA \right)\!\!\left(\iint_S \,dA \right) = S\!\left(\iint_S x^2\,dA \right) = \iint_S \iint_S x_2^2\,dA_1\,dA_2$ 이고,
• $\displaystyle\iint_S \iint_S x_1 x_2\,dA_1\,dA_2 = \left(\iint_S x_1\,dA_1 \right)\!\!\left(\iint_S x_2\,dA_2 \right) = \left(\iint_S x\,dA \right)^2$가 된다.
• 마찬가지로, $y_1^2,\, y_2^2$항의 적분은 각각 $\displaystyle S\!\left(\iint_S y^2\,dA \right)$이고, $y_1 y_2$ 항의 적분은 $\displaystyle\left(\iint_S y\,dA \right)^2$이다.

 

즉 $A = \displaystyle\iint_S x^2 + y^2\,dA,\, B = \iint_S x\,dA,\, C = \iint_S y\,dA$라 하면

$$E = \dfrac{1}{S^2}\!\left(2AS - 2B^2 - 2C^2 \right) \quad \cdots\ (\star)$$

로 정리가 된다!

 

  일단, 다각형의 넓이 $S$는 벡터의 외적을 이용하여 $\mathcal O(N)$에 구할 수 있다. 이제 우리의 과제는 $A,\, B,\, C$를 구하는 것인데, 주어진 도형이 다각형이기에 그대로 이중적분을 계산하는 것은 굉장히 힘들다. 중적분을 다른 형태의 적분으로 바꿔야 할 필요성을 느끼고, 이로부터 그린 정리(Green's Theorem)를 이용하려는 생각을 할 수 있다. 그리고 본 문제에서는 그린 정리의 전제 조건(1계 편도함수의 연속성 등)을 모두 만족하므로, 실제로 그린 정리를 사용해서 이중적분을 선적분으로 바꿀 수 있다.

 

  먼저 $A$를 살펴보면, 그린 정리에 의해(적분 방향이 반시계 방향이 되어야 함에 주의하라)

$$A = \displaystyle\oint_{\partial S} - \dfrac{1}{3}y^3\,dx + \dfrac{1}{3}x^3 \,dy = \dfrac{1}{3}\sum_{i=1}^N \int_{(x_i,\, y_i)}^{(x_{i+1},\, y_{i+1})} x^3\,dy - y^3\,dx$$

가 되고(이때 $(x_i,\, y_i)$는 다각형의 $i$번째 꼭짓점이며, $N+1$번째 점은 첫 번째 점으로 생각하자), $i$번째 변은

$$y = \dfrac{y_{i+1} - y_i}{x_{i+1} - x_i} (x - x_i) + y_i$$

로 표현 가능하므로 $dy = \dfrac{y_{i+1} - y_i}{x_{i+1} - x_i} dx,\, dx = \dfrac{x_{i+1} - x_i}{y_{i+1} - y_i} dy$가 된다. 이를 각각 첫 번째, 두 번째 항에 대입하고 정적분을 계산하면

$$A = \dfrac{1}{12}\sum_{i=1}^N \left\{(y_{i+1} - y_i)(x_i^3 + x_i^2 x_{i+1} + x_i x_{i+1}^2 + x_{i+1}^3 ) - (x_{i+1} - x_i)(y_i^3 + y_i^2 y_{i+1} + y_i y_{i+1}^2 + y_{i+1}^3 ) \right\}$$

가 된다.

 

  이쯤에서 멈춰도 충분하지만, 식을 조금 더 간단히 만들 수 있다. 앞쪽의 곱셈을 전개한 항 중, $x_{i+1}^3 y_{i+1} - x_i^3 y_i$에 주목해 보자. 이 항들은 같은 꼴에 첨자만 다르므로, 이웃한 항을 고려한다면 망원 급수의 형태로 상쇄되어 사라질 것이다. 따라서 남는 항을 정리해 보면

$$x_{i+1}^2 x_i y_{i+1} + x_{i+1} x_i^2 y_{i+1} + x_i^3 y_{i+1} - x_{i+1}^3 y_i - x_{i+1}^2 x_i y_i - x_{i+1} x_i^2 y_i \\ = (x_i y_{i+1} - x_{i+1} y_i)(x_i^2 + x_i x_{i+1} + x_{i+1}^2)$$

로 깔끔하게 묶이는 걸 확인할 수 있다! 뒤의 곱셈식은 여기에서 $x,\, y$의 위치만 바꾸면 되므로 이를 대입하면…

$$\therefore\ A = \displaystyle\dfrac{1}{12}\sum_{i=1}^N (x_i y_{i+1} - x_{i+1} y_i)(x_i^2 + x_i x_{i+1} + x_{i+1}^2 + y_i^2 + y_i y_{i+1} + y_{i+1}^2)$$

 

  한편 $B,\, C$에 대한 식도 위와 비슷한 방식으로 유도할 수 있고(이는 스스로 계산해 보길 바란다), 이를 $(\star)$에 넣으면 우리가 구하고자 했던 기댓값이 나오게 된다. 남은 것은 계산하는 과정을 코드로 옮기는 일뿐이다. 여기까지 잘 도달한 사람들은, 오버플로우만 조심한다면 코드를 작성하는 데는 큰 어려움이 없을 것이다.

 

 

  풀어보면 알겠지만, 계산하는 과정이 길고 복잡했던 것에 비해 코드 자체는 간단하다. 수학 문제의 '식 정리를 많이 할수록 코드는 짧아지는 특성'을 단적으로 보여주는 예라 할 수 있겠다.