[Python] BOJ 17441 - 파리채 만들기

snowflake 님의 풀이를 보고 영감을 받아 작성한 글입니다.

문제에서 제시한 내용은 어떤 다각형이 주어질 때, 다각형 내의 임의의 두 점 사이 거리 제곱의 기댓값을 구하라는 것입니다.

다각형 내의 점은 연속적으로 분포하므로 적분을 사용해주어야 합니다.

다각형의 넓이를 $S$라고 하고, 임의의 두 점의 좌표를 각각 $(x_1,y_1),$ $(x_2,y_2)$ 라 정의해줍니다.

이 때, 두 점 사이 거리의 제곱은 $(x_1-x_2)^2+(y_1-y_2)^2$이고, 두 점 주변의 미소면적

를 잡았을 때,

전체 다각형 영역 중에서 각 미소면적 내의 점을 독립적으로 하나씩 택할 확률은

라는 사실을 쉽게 알아낼 수 있습니다.

이 후, 기댓값 $E$는

라는 적분식으로 계산될 수 있습니다. 여기서 조금 더 하면

• $\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_1y_2$ 항을 적분하면 $\displaystyle\left(\iint_S y\,dA \right)^2$라는 식이 됩니다.

이 때,

라고 정의하면 E에 대해

라고 정리할 수 있습니다.

이 때, 이중적분을 그대로 계산하는 것은 힘듭니다. 그러므로 우리는 이 이중적분을 선적분으로 바꾸어줄 필요가 있습니다. 이를 그린 정리를 활용하여 진행할 것입니다.

$A$는 그린 정리에 의하여

가 됩니다. 이 때 $(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$ 로 표현 가능하므로

가 됩니다. 이를 첫 번째와 두 번째 항에 대입하고 정적분을 계산하면

가 됩니다. 여기서 식을 더 정리해봅시다.

위와 같은 과정을 $B,C$ 에서도 진행할 수 있고, 이를 위의 식에 삽입하면 문제의 답인 기댓값을 얻을 수 있습니다.

a = n_x = n_y = i_x = i_y = 0
n = int(input())
x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())
for i in range(1, n - 1):
    a += ((x[i] - x[0]) * (y[i + 1] - y[0]) - (x[i + 1] - x[0]) * (y[i] - y[0])) / 2
for i in range(n):
    n_x += ((x[(i + 1) % n] ** 3 + x[(i + 1) % n] ** 2 * x[i] + x[(i + 1) % n] * x[i] ** 2 + x[i] ** 3) * (y[(i + 1) % n] - y[i])) / 12
    n_y += ((y[(i + 1) % n] ** 3 + y[(i + 1) % n] ** 2 * y[i] + y[(i + 1) % n] * y[i] ** 2 + y[i] ** 3) * (x[(i + 1) % n] - x[i])) / -12
    i_x += ((x[(i + 1) % n] ** 2 + x[(i + 1) % n] * x[i] + x[i] ** 2) * (y[(i + 1) % n] - y[i])) / 6
    i_y += ((y[(i + 1) % n] ** 2 + y[(i + 1) % n] * y[i] + y[i] ** 2) * (x[(i + 1) % n] - x[i])) / -6
print((a * n_x + a * n_y - i_x ** 2 - i_y ** 2) * 2 / a ** 2)