BOJ 16642 Cake Cutting

먼저 반지름을 $R$로 나누어 단위원으로 만들어 줍니다. 그러면 이 단위원을 세로로 자른 영역의 면적은 다음과 같이 구할 수 있습니다.

위의 값을 $f(l, r)$이라고 합시다.

이제 각 영역 내에서 cost function을 최소화하는 값을 구해야 합니다. $i$번째 영역의 왼쪽과 오른쪽 경계를 각각 $x = l, x = r$이라고 하고, $x < l$과 $x > l$의 영역에 있는 빵과 크림의 양을 각각 $V_l, V_r, v_l, v_r$이라고 하면, cost function은 다음과 같이 적을 수 있습니다.

이는 $f(l, x)$에 대한 이차함수이며, $h$와 $b_i$가 모두 양수이므로 이 함수는 미분값이 0이 되는 지점 $f(l, x) = \frac{h (V_r - V_l) + b_i (v_r - v_l)}{2h^2 + 2b_i^2}$에서 최솟값을 갖습니다. $f(l, x)$는 $l \le x \le r$에서 $0 \le f(l, x) \le f(l, r)$로 단조증가하므로, 이 지점이 이 범위 내에 있다면 위의 cost function에 직접 대입하여 극값을 얻을 수 있습니다. 그렇지 않다면 양 끝점을 대입해본 값을 확인합니다.

풀이를 시작할 때 길이를 $R$로 나누었으므로 최종 출력값을 보정해 줘야 하는데, 구하는 값은 길이의 네제곱의 차원을 가지므로 $R^4$를 곱해서 출력하면 됩니다.

그런데 이 문제에서는 실수 오차도 주의해야 합니다. 특히 입력값으로부터 $\arcsin x$를 구하는 과정에서 실수 오차가 크게 증폭될 수 있습니다. 입력값이 최대 소수점 이하 3자리까지 들어온다는 점을 이용하여, 입력에 1000을 곱한 값을 정수로 만들어서 누적 합을 구한 다음 $1000R$로 나누어 $\arcsin$ 함수의 입력으로 사용하여야 실수 오차에 의한 WA를 피할 수 있습니다.