[Python] 백준 16995 - Piece of Cake

https://www.acmicpc.net/problem/16995

풀이

이전 포스팅에서 다룬 신발끈 공식의 특성을 창의적으로 이용하는 문제이다.

 

처음에는 이런 생각을 했다.

볼록 K각형은 K-2개의 삼각형으로 이루어져있음을 이용해서

"대칭적으로, 가능한 모든 조합의 삼각형을 다 더했을 때 전체 다각형의 넓이와 관련해서 간단하게 식이 나오지 않을까?"

 

안나왔다. 이것때문에 몇시간을 고민했다.

사실 나오긴 나오는데 이걸 수학적으로 계산하려니 머리가 아팠다.

 

그래서 조금 다른 접근을 소개한다.

 

신발끈 공식과 넓이 계산

 

예를 들어서 N = 6, K = 4라고 해보자.

즉, 육각형(여섯모) 내에서 4개의 점을 잡아 사각형(네모)를 만드는 것이다.

 

예를 들어서, A, C, D, F의 사각형을 골랐다고 해보자.

그러면 우리는 사각형 ACDF의 넓이를 신발끈 공식을 이용해서 구해줄 수 있다.

이때 계산 과정을 잘 보면,

AC, CD, DF, FA 4개의 선분에 대해서 반시계방향(혹은 시계방향)으로 원점 O가 있다고 가정하고 외적을 해서 더한다.

즉, $x_{1}y_{2} - x_{2}y_{1}$ 꼴의 식을 4개를 더하는 것이다.

 

그러니까, 각 변에 대해서, 해당 변이 포함된 도형의 넓이를 계산할 때 마다 해당 식을 한 번 더해주는 것이다.

 

 

이제 확률의 선형성에 대해서 잠시 관찰해보자.

 

확률 계산과 넓이와의 관계

 

AB변이 포함된 도형이 세 개가 있다고 가정하자. (물론 그 도형들은 AB변 말고도 다른 변으로도 이루어져 있을 것이다.)

각각 1번, 2번, 3번 도형이라고 하고 해당 도형이 선택될 확률은 각각 1/2, 1/6, 1/5이라고 하자.

 

그렇다면 나중에 최종 도형의 기댓값을 계산하기 위해서 다음과 같은 식을 계산하게 될 것이다. (일단은 다른 것은 제쳐두고 AB변이 포함된 도형 3개만 생각해보자)

 

E = (1번도형넓이)*1/2 + (2번도형넓이)*1/6 + (3번도형넓이)*1/5

 

그런데, 각 도형의 넓이는 AB변의 외적을 포함해서, 다른 변들까지 외적들의 합으로 나타내져있다.

그러니까 우리는 이 식을 선형결합으로 생각해서, 전개해주고

AB변에 대해서만 생각해보면 AB변에 대한 외적식이 총합 (1/2 + 1/6 + 1/5)번 더해져있는 것이다.

 

그러니까, 이 말은 곧

모든 가능한 변에 대해서 해당 변의 외적에다가, 그 변이 선택될 확률을 곱한 것을 더한 것이 답이 된다는 소리이다!

 

조합과 변이 선택될 확률

사실 생각해보면 AC가 선택될 확률과 BD가 선택될 확률, CE가 선택될 확률....은 모두 같다.

그러니까 (같은 거리 만큼 떨어져있는 점) 끼리는 확률이 모두 같다.

시간초과를 방지해주기 위해 각 거리별로 확률을 한 번씩만 계산해주고 나중에 곱하자.

 

예를 들어 AC(거리2)인 변이 선택될 확률은 무엇인가?

점 A와 점 C 사이(ABC 구간)에서는 A, C말고 달리 선택된 점이 없어야 한다. 즉, A와 C가 이웃한 경우만 보자.

 

그리고 ABC구간을 제외한 DEF구간에서 나머지 점 2개를 선택하는 것이다.

그러면 이 경우 분자는

3C2가 된다. 조금 일반화해보면 (N-거리-1)C(K-2)가 된다. (거리 개념의 구현은 마음대로 해도 된다. 실제로 아래 코드에는 조금 다르게 했다. 식만 적절히 변형하자.)

 

분모는 전체 경우, 즉 NCK가 된다.

 

이렇게 모든 "거리"에 대해서 확률을 계산해주고 나면

 

이중 반복문을 돌며 가능한 모든 변에 대해서 외적식을 구하고, 거리에 알맞는 확률을 곱해서 더해주면 된다.

 

이렇게 얻은 값에다가 0.5를 곱해주고(신발끈공식!!), 절댓값을 씌워주면 최종 답을 얻을 수 있다.

 

from math import comb

N, K = map(int, input().split())
dots = []
for i in range(N):
    x, y = map(float, input().split())
    dots.append((x, y))

d = comb(N, K)
prob = [comb(N-j-2, K-2)/d for j in range(N-1)]

total = 0
for i in range(N):
    for j in range(N-1): #j는 간격(여기서는 0부터 시작)
        x1, y1 = dots[i]
        x2, y2 = dots[(i+j+1)%N]
        total += (x1*y2 - x2*y1)*prob[j]

print(0.5 * abs(total))